并查集的基本操作：
1.find，查询一个元素属于哪一个集合。
2.merge 把两个集合合并成一个大集合，一般不用写一个额外的函数，直接写主函数内就可以了。
在并查集中，我们采用“待元法”，即为每个集合选择一个固定的元素，作为整个集合的“代表”。使用一个树形结构存储每个集合，书上每个结点都是一个元素，树根是集合的代表元素。
poj 2524
一个基础的例题。
题意：多组输入，处理到文件末尾，每组输入一个n、m，表示有n个同学，m个关系，每个关系输入a、b，表示a、b是相同的宗教，问有多少个不同的宗教。
思路：合并每个a、b的集合，最后遍历1 ~ n，有多少个不同的集合就有多少个不同的宗教。fa[i]的初始值可以是i也可以是-1或者0，赋值为0有时可以偷懒，赋值-1和0是为了可以直接用memset初始化，但是容易出错，出错的一个原因是数据输入中有重边。这里还用到了路径压缩和按秩合并。
原理：
1.路径压缩，每次访问find的操作的同时，把访问过的每个结点直接指向树根，这样下次查找会更快，同时可以避免某条路径特别长。
2.按秩合并，也称“启发式合并”，“秩”定义为树的深度，把“秩”较小的树根作为“秩”较大的树根的子结点，这样就是真正的菊花图了，路径合并还是会出现一条路径比较长的情况（这条路径一直没查询到）。数据1e7的时候用会超内存，1e5的时候最佳，小于1e5几乎没有效果。
3.单独用1或者2，复杂度 （log n），两个都用复杂度就是反阿克曼函数级别的了，是一个比对数函数增长还慢的函数。
COde：
#include<iostream>
using namespace std;
int fa[500005],ran[500005];
inline void init(int n){
for(int i=1;i<=n;i++){
fa[i]=i;
ran[i]=1;
}
}
int find(int x){
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
inline void merge(int i,int j){
int x=find(i),y=find(j);
if(ran[x]<=ran[y])
fa[x]=y;
else
fa[y]=x;
if(ran[x]==ran[y]&&x!=y)
ran[y]++;
}
int main(){
int n,m,a,b,i,j=1;
while(cin>>n>>m&&(n||m)){
init(n);
for(i=1;i<=m;i++){
cin>>a>>b;
merge(a,b);
}
int ans=0;
for(i=1;i<=n;i++) if(fa[i]==i) ans++;
cout<<"Case "<<j++<<": "<<ans<<endl;
}
} poj 1611
题意：
多组输入，每组输入一个n、m，表示n个学生编号0~n-1，分为m组，每组开头一个数字k表示该组有k个同学，问编号为0的同学的那组有多少人，输入以n=0，m=0结束。
思路：
直接合并，让0始终为根，因为数据较小，不需要按秩合并，效果不大。
Code：
#include<iostream>
using namespace std;
int fa[500005];
inline void init(int n){
for(int i=0;i<=n-1;i++){
fa[i]=i;
}
}
int find(int x){
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
inline void merge(int i,int j){
int x=find(i),y=find(j);
if(x==0) fa[y]=x;
else fa[x]=y;
}
int main(){
int n,m,a,b,k,i;
while(cin>>n>>m&&(n||m)){
init(n);
while(m--){
cin>>k;
for(i=1;i<=k;i++){
if(i!=1){
cin>>b;
merge(a,b);
a=b;
continue;
}
cin>>a;
}
}
int ans=0;
for(i=0;i<=n-1;i++) if(find(i)==0) ans++;
cout<<ans<<endl;
}
} poj 1703
题意：T组数据，每组数据输入n、m，n，n个罪犯编号1 ~ n，m组操作，D表示A、B不是一个集合的，A表示询问你A、B是一个集合还是不是一个集合又或是还不确定。
思路：比较有趣，并查集擅长动态维护许多具有传递性的关系，等于是连续性的，不等于不是连续性的，因为A、B的关系只有两种，所以A、B不是一个集合可以转化为A和B的对头是一个集合的、B和A的对头是一个集合的，开两倍的数组进行维护，那么就有传递性了。
Code：
#include<iostream>
#include<cstdio>
using namespace std;
#define N 100005
int fa[2*N],ran[2*N];
inline void init(){
for(int i=1;i<=2*N;i++){
fa[i]=i;
ran[i]=1;
}
}
int find(int x){
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
inline void merge(int i,int j){
int x=find(i),y=find(j);
if(x==y) return;
if(ran[x]<=ran[y])
fa[x]=y;
else
fa[y]=x;
if(ran[x]==ran[y])
ran[y]++;
}
int main(){
int t,n,m,a,b,i;
char ch;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
init();
while(m--){
scanf(" %c%d%d",&ch,&a,&b);
if(ch=='D'){
merge(a,b+N);
merge(a+N,b);
}
else{
if(find(a)==find(b))
printf("In the same gang.\n");
else if(find(a)==find(b+N))
printf("In different gangs.\n");
else{
puts("Not sure yet.");
}
}
}
}
} poj 2236
题意：给你N台电脑，从1-N。一个数字，表示两台计算机的最大通信距离，超过这个距离就无法进行通信。然后分别告诉这些电脑的坐标，接下来有两种操作，第一种O表示这点电脑修好，第二种S，表示测试这两台电脑能不能进行正常的通信.
思路：存储修复的电脑，每修复一个电脑就判断能否和前面的电脑合并。
思路：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 1001
int fa[N],ran[N],a[1001],b[1001],em[1001];
inline void init(int x){
for(int i=1;i<=x;i++){
fa[i]=i;
ran[i]=1;
}
}
int find(int x){
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
inline void merge(int i,int j){
int x=find(i),y=find(j);
if(x==y) return;
if(ran[x]<=ran[y])
fa[x]=y;
else
fa[y]=x;
if(ran[x]==ran[y])
ran[y]++;
}
int check(int x,int y,int a,int b,int d){
int temp=(x-a)*(x-a)+(y-b)*(y-b);
if(temp>d*d) return 0;
return 1;
}
int main(){
int n,d,i,aa,bb,m,j=0;
char ch;
scanf("%d%d",&n,&d);
init(n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
while(~scanf(" %c",&ch)){
if(ch=='O'){
scanf("%d",&m);
for(i=1;i<=j;i++){
int temp=em[i];
if(check(a[temp],b[temp],a[m],b[m],d))
merge(temp,m);
}
em[++j]=m;
}
else{
scanf("%d%d",&aa,&bb);
if(find(aa)==find(bb)) printf("SUCCESS\n");
else
printf("FAIL\n");
}
}
} poj 2492
题意：给出N条虫子，然后a和b交配，给出M对a和b后问有没有同性恋的虫子(题目意思太BT了）。
思路：和poj 1703一样的思路，只是如果发现a、b是同性（也就是一个集合）的，后面就不用判断，输出有同性恋就可以了。
Code：
#include<iostream>
#include<cstdio>
using namespace std;
#define N 2123
int fa[2*N],ran[2*N];
inline void init(){
for(int i=0;i<=2*N;i++){
fa[i]=i;
ran[i]=1;
}
}
int find(int x){
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
inline void merge(int i,int j){
int x=find(i),y=find(j);
if(x==y) return;
if(ran[x]<=ran[y])
fa[x]=y;
else
fa[y]=x;
if(ran[x]==ran[y])
ran[y]++;
}
int main(){
int t,n,m,a,b,i,j=1;
scanf("%d",&t);
while(t--){
int flag=1;
scanf("%d%d",&n,&m);
init();
while(m--){
if(flag){
scanf("%d%d",&a,&b);
int x=find(a),y=find(b);
if(x==y)
flag=0;
else{
merge(a,b+N);
merge(a+N,b);
}
}
else
scanf("%*d%*d");
}
if(j>1)
printf("\n");
printf("Scenario #%d:\n",j++);
if(!flag) printf("Suspicious bugs found!\n");
else printf("No suspicious bugs found!\n");
}
return 0;
} poj 1988
题意：有n个元素，开始每个元素自己一栈，有两种操作，将含有元素x的栈放在含有y的栈的顶端，合并为一个栈。第二种操作是询问含有x元素下面有多少个元素。
思路：将含有元素x的栈的父结点设为含有y的栈，用ran[x]记录此时x下面的元素个数，size[y]表示此时含有y的栈的元数个数。
Code:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int fa[30005],ran[30005],size[30005];
inline void init(){
for(int i=1;i<=30005;i++){
fa[i]=i;
ran[i]=0;
size[i]=1;
}
}
int find(int x){
if(x==fa[x]) return x;
else{
int t=fa[x];
fa[x]=find(fa[x]);
ran[x]+=ran[t];
return fa[x];
}
}
inline void merge(int i,int j){
int x=find(i),y=find(j);
fa[x]=y;
ran[x]+=size[y];
size[y]+=size[x];
}
int main(){
int t,a,b;
char ch;
init();
scanf("%d",&t);
while(t--){
scanf(" %c",&ch);
if(ch=='M'){
scanf("%d%d",&a,&b);
merge(a,b);
}
else{
scanf("%d",&a);
find(a);
printf("%d\n",ran[a]);
}
}
} poj 1182
题意：根据动物之间的吃与被吃关系通过并查集把他们连起来，输出语句出现矛盾的次数，默认先输入的正确（此矛盾包括：1、自身矛盾，2、与N矛盾）。（并查集的经典题）
思路：出处 别人的博客。非常详细。
如果两个数在同一个集合（在这里同一个集合表示两者关系已经确定了）里或者自身矛盾已经与N矛盾，直接判断真假，没出现过就把他们合并到一个区间。
合并树时要注意顺序，我这里是把 x 树的根当做主根。找父亲节点时，要不断更新 r[]的值。这里有两个关系：如果 x 和y 为关系 r1, y 和 z 为关系 r2 ，那么 x 和z的关系就是 （r1+r2）%3。
x和fx的关系是ran[x]，y和fy的关系是ran[y]，y和x的关系是d-1（d=0表示相等，d=1，d=1表示a被b吃，d=2表示a吃b），那么fy 对 fx 的关系是（3-r[y] + d-1 + r[x]）%3。
Code:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 50000
int fa[N],ran[N],n;
inline void init(){
for(int i=1;i<=n;i++){
fa[i]=i;
ran[i]=0;
}
}
int find(int x){
if(x==fa[x])
return x;
int t=fa[x];
fa[x]=find(fa[x]);
ran[x]=(ran[x]+ran[t])%3;
return fa[x];
}
inline void merge(int i,int j,int d){
int x=find(i),y=find(j);
if(x==y) return;
fa[y]=x;
ran[y]=(3-ran[j]+d-1+ran[i])%3;
}
int main(){
int m,a,b,d,i,ans=0;
scanf("%d%d",&n,&m);
init();
while(m--){
scanf("%d%d%d",&d,&a,&b);
if(a>n||b>n||(d==2&&a==b)) ans++;
else if(find(a)==find(b)){
if(d==1&&ran[a]!=ran[b]) ans++;
if(d==2&&(ran[a]+1)%3!=ran[b]) ans++;
}
else
merge(a,b,d);
}
printf("%d\n",ans);
} hdu 3635
题意：起初球i是被放在i号城市的，在年代更迭，世事变迁的情况下，球被转移了，而且转移的时候，连带该城市的所有球都被移动了：T A B（A球所在的城市的所有球都被移动到了B球所在的城市），Q A（问：A球在那城市？A球所在城市有多少个球呢？A球被转移了多少次呢？）。
思路；一个数组size[x]记录以x为代表的集合的元数个数，ran[x]则记录x被搬运地方次数。
Code：
#include<iostream>
#include<cstdio>
using namespace std;
int fa[10005],ran[10005],size[10005];
inline void init(int n){
for(int i=1;i<=n;i++){
fa[i]=i;
ran[i]=0;
size[i]=1;
}
}
int find(int x){
if(x==fa[x]) return x;
else{
int t=fa[x];
fa[x]=find(fa[x]);
ran[x]+=ran[t];
return fa[x];
}
}
inline void merge(int i,int j){
int x=find(i),y=find(j);
fa[x]=y;
size[y]+=size[x];
ran[x]++;
}
int main(){
int t,n,q,j=1;
char ch;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&q);
printf("Case %d:\n",j++);
init(n);
while(q--){
int a,b;
scanf(" %c",&ch);
if(ch=='T'){
scanf("%d%d",&a,&b);
merge(a,b);
}
else{
scanf("%d",&a);
int ans=find(a);
printf("%d %d %d\n",ans,size[ans],ran[a]);
}
}
}
return 0;
} hdu 1856
题意：通俗点讲就是有几个人，他们每个人有自己的小团体，要你求他们中人数最多的数量
思路：离散化后可以按秩合并，没有离散化就不能按秩合并，size[x]记录这个集合的元素个数，每次合并时记录最大值就可以了。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int fa[10000005],size[10000005];
inline void init(){
for(int i=1;i<=10000000;i++){
fa[i]=i;
size[i]=1;
}
}
int find(int x){
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
inline int merge(int i,int j){
int x=find(i),y=find(j);
if(x!=y){
fa[x]=y;
return size[y]+=size[x];
}
else
return size[y];
}
int main(){
int n,a,b,i;
while(~scanf("%d",&n)){
if(n==0){
printf("1\n");
continue;
}
int ans=0;
init();
for(i=1;i<=n;i++){
scanf("%d%d",&a,&b);
ans=max(ans,merge(a,b));
}
printf("%d\n",ans);
}
} hdu 1272
题意：给不知道多少对无向边，构成一条边，问是否联通且无环。（重边也是输出no）
思路：合并时判断有无成环，如果没有成环就判断所有的边是否联通。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int fa[100005],ran[100005],vis[100005];
inline void init(){
for(int i=1;i<=100000;i++){
fa[i]=i;
ran[i]=1;
vis[i]=0;
}
}
int find(int x){
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
inline int merge(int i,int j){
int x=find(i),y=find(j);
if(x==y) return 0;
fa[x]=y;
return 1;
}
int check(){
int i,x,flag=0;
for(i=1;i<=100005;i++)
if(vis[i]){
if(flag){
if(find(i)!=x){
return 0;
}
}
else{
x=find(i);
flag=1;
}
}
return 1;
}
int main(){
int a=0,b=0,i;
while(a!=-1){
int flag=1;
init();
while(scanf("%d%d",&a,&b),a&&a!=-1){
vis[a]=vis[b]=1;
if(flag)
flag=merge(a,b);
}
if(flag==0)
printf("No\n");
else if(a!=-1){
if(check())
printf("Yes\n");
else
printf("No\n");
}
}
} hdu 1325
题意：和1272一样的输入，但是这里是有向边，第一个整数指向第二个整数。
思路：不能成环，全部联通，任何一个节点的入度不能大于1，重边不要紧。
Code：
#include<stdio.h>
#include<string.h>
#define N 11000
int fa[N],vis[N],maxn;
void init(){
for(int i=1;i<N;i++)
fa[i]=i;
memset(vis,0,sizeof(vis));
maxn=0;
}
int find(int x){
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
int merge(int i,int j,int flag){
int x=find(i),y=find(j);
if(x==y||y!=j) return 0;//入度不为1
fa[y]=x;
return flag;
}
int max(int a,int b){
return a>b?a:b;
}
int main(){
int a,b,j=1,flag=1;
init();
while(~scanf("%d%d",&a,&b)&&a!=-1){
if(!a){
int ans=0;
for(int i=1;i<=maxn;i++)
if(vis[i]&&i==fa[i]) ans++;
if(ans<=1&&flag)
printf("Case %d is a tree.\n",j++);
else
printf("Case %d is not a tree.\n",j++);
init();
flag=1;
continue;
}
vis[a]=vis[b]=1;
maxn=max(maxn,max(a,b));
flag=merge(a,b,flag);
}
} hdu 1198
题意：A ~ K 代表n个管道图，给出一个m * n的二维字符数组，判断当整个图都能流到水时需要放几口井。
思路：判断每个点和它右边、下边是否可以合并，可以就合并，最后判断有几个联通块就可以了。
Code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include <vector>
#include<map>
#include<set>
#include<utility>
#define js ios::sync_with_stdio(false)
using namespace std;
int fa[2510];
char mapp[55][55];
int find(int x) {
return fa[x]==-1?x:(fa[x]=find(fa[x]));
}
int main() {
int n,m;
while(scanf("%d%d",&n,&m),n+1) {
memset(fa,-1,sizeof fa);
for(int i=0;i<n;++i) scanf("%s",mapp[i]);
for(int i=0;i<n;++i)
for(int j=0;j<m;++j) {
if(j!=m-1) {
if(mapp[i][j]=='B'||mapp[i][j]=='D'||mapp[i][j]=='F'||mapp[i][j]=='G'||mapp[i][j]=='I'||mapp[i][j]=='J'||mapp[i][j]=='K')
if(mapp[i][j+1]=='A'||mapp[i][j+1]=='C'||mapp[i][j+1]=='F'||mapp[i][j+1]=='G'||mapp[i][j+1]=='H'||mapp[i][j+1]=='I'||mapp[i][j+1]=='K') {
int x=find(i*m+j+1),y=find(i*m+j+2);
if(x!=y) fa[y]=x;
}
}
if(i!=n-1) {
if(mapp[i][j]=='C'||mapp[i][j]=='D'||mapp[i][j]=='E'||mapp[i][j]=='H'||mapp[i][j]=='I'||mapp[i][j]=='J'||mapp[i][j]=='K')
if(mapp[i+1][j]=='A'||mapp[i+1][j]=='B'||mapp[i+1][j]=='E'||mapp[i+1][j]=='G'||mapp[i+1][j]=='H'||mapp[i+1][j]=='J'||mapp[i+1][j]=='K') {
int x=find(i*m+j+1),y=find(i*m+j+m+1);
if(x!=y) fa[y]=x;
}
}
}
int ans=0;
for(int i=1;i<=n*m;++i) if(find(i)==i) ans++;
printf("%d\n",ans);
}
} hdu 2586
题意：一个村子里有n个房子，这n个房子用n-1条路连接起来，接下了有m次询问，每次询问两个房子a,b之间的距离是多少。
思路：最近公共祖先或者并查集+深搜。因为数据弱，我并查集的思路很简单，不去路径合并（其实路径合并也可以），size[x]=d，表示x到父结点的距离是d，询问的时候算出每个结点到根的距离，然后相减就可以了。
Code：
LCA代码戳我
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include <vector>
#include<map>
#include<set>
#include<utility>
#define js ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
int fa[40005],size[40005],ans1=0,ans2=0;
inline init(int x){
for(int i=1;i<=x;++i) {
fa[i]=i;
size[i]=0;
}
}
void merge(int i,int j,int d) {
if(size[i]) {
fa[j]=i;
size[j]=d;
}
else {
fa[i]=j;
size[i]=d;
}
}
int find1(int x){
if(fa[x]==x) return ans1;
ans1+=size[x];
find1(fa[x]);
}
int find2(int x){
if(fa[x]==x) return ans2;
ans2+=size[x];
find2(fa[x]);
}
int main() {
int t,n,m;
js;
cin>>t;
while(t--) {
int a,b,c;
cin>>n>>m;
init(n);
for(int i=1;i<=n-1;++i) {
cin>>a>>b>>c;
merge(a,b,c);
}
for(int i=1;i<=m;++i) {
cin>>a>>b;
ans1=ans2=0;
cout<<abs(find1(a)-find2(b))<<endl;
}
}
} hdu 6109
题意：m条信息由ans组数据组成，每条信息的最后一个整数e=1表示A、B相等，e=0表示A、B不相等，每组数据加上最后一条信息就会矛盾，不加上就不会矛盾，问ans的值，并输出每组输出有几条信息。
思路：用set存出现过的数字，便于找下一组数据之前初始化，再用一个set存结点i的对头，每次合并时将被合并的数的对头移到父亲的对头集合里，再把被合并的数从对头的对头集合里抹掉。如果x、y是相等的，但是不是一个集合或y是x的对头，或x、y不相等，但是x、y是一个集合的，那么这是一组数据的结尾。（理论上是可以开两倍的fa[]数组去写不用set，就和1703的思路差不多，但是这是很久以前写的，我也就没试，江大佬亲自验证是错的）
Code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include <vector>
#include<map>
#include<set>
#include<utility>
#define js ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
int fa[100005],ran[100005],ans[100005];
set<int>st;
set<int>s[100005];
inline void init(){
set<int>::iterator it;
for(it=st.begin();it!=st.end();++it) {
fa[*it]=-1;
ran[*it]=1;
s[*it].clear();
}
st.clear();
}
int find(int x) {
return fa[x]==-1?x:(fa[x]=find(fa[x]));
}
void merge(int i,int j) {
if(i==j) return;
set<int>::iterator it;
if(ran[i]==0) ran[i]=1;
if(ran[j]==0) ran[j]=1;
if(ran[i]>ran[j]) {
for(it=s[j].begin();it!=s[j].end();it++) {
s[*it].erase(j);
s[*it].insert(i);
s[i].insert(*it);
}
fa[j]=i;
}
else{
for(it=s[i].begin();it!=s[i].end();it++) {
s[*it].erase(i);
s[*it].insert(j);
s[j].insert(*it);
}
fa[i]=j;
}
if(ran[i]==ran[j]) ran[j]++;
}
int main() {
int T,a,b,e,x,y,sum=0,jy=0;
js;
cin>>T;
memset(fa,-1,sizeof fa);
while(T--) {
cin>>a>>b>>e;
st.insert(a),st.insert(b);
x=find(a),y=find(b);
sum++;
if(e==1) {
if(x==y||s[x].count(y)==0) {
merge(x,y);
}
else {
ans[++jy]=sum;
sum=0;
init();
}
}
else {
if(x==y) {
ans[++jy]=sum;
sum=0;
init();
}
else {
s[x].insert(y);
s[y].insert(x);
}
}
}
cout<<jy<<endl;
for(int i=1;i<=jy;++i) cout<<ans[i]<<endl;
return 0;
} 
京公网安备 11010502036488号