当前位置: 代码迷 >> 综合 >> 并查集(待更新)
  详细解决方案

并查集(待更新)

热度:3   发布时间:2024-01-15 07:10:58.0

并查集是一种比较简单的数据结构,它可以动态维护若干个不重叠的集合,并支持合并与查找。

具体原理解释:《算法进阶指南》讲的就很不错,网上资料也很多,这里就只给出题。

理解关键点:fa[i]=x 表示i的父亲结点为x,根节点的父亲结点为自己

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>using namespace std;
const int N=5e5+5;
int fa[N],sizee[N],rankk[N],deep[N],timee[N],tim;
//sizee[i]:以i为根的集合大小
//rankk:秩,
int findd(int x)
{if(x==fa[x]) return x;else{   int f=findd(fa[x]);deep[x]=deep[fa[x]]+1;return f;}}
void mergee(int x,int y)
{tim++;int t1=findd(x);int t2=findd(y);if(t1!=t2){if(rankk[t2]<rankk[t1])swap(t1,t2);fa[t1]=t2;sizee[t2]+=sizee[t1];timee[t1]=tim;rankk[t2]=max(rankk[t2],rankk[t1]+1);}
}
int query(int x,int y)
{int ans=0;int t1=findd(x);int t2=findd(y);if(t1!=t2) return 0;else{while(x!=y){if(deep[x]<deep[y]) swap(x,y);ans=max(ans,timee[x]);x=fa[x];	}return ans;}}
int main()
{int n,m;while(scanf("%d%d",&n,&m)!=-1){for(int i=1;i<=n+1;i++){fa[i]=i;sizee[i]=1;rankk[i]=0;deep[i]=0;timee[i]=0;}int ans=0;while(m--){int op,x,y;scanf("%d%d%d",&op,&x,&y);x^=ans;y^=ans;if(op==0){mergee(x,y);}else{ans=query(x,y);printf("%d\n",ans);}}}return 0;
}

经典例题:

1.基础并查集:

作用:一张无向图维护节点之间的连通性

路径优化 并查集【例4-7】亲戚(relation)  (递归+非递归+路径压缩)

二维并查集 例4-8】格子游戏                      (比较有意思的二维并查集判断环)

[luogu 1955] [NOI2015]程序自动分析         (并查集+离散化)

HDU - 5606 tree                   并查集求连通块的元素个数

  相关解决方案