并查集是一种高效的数据结构，主要用来维护不同对象之间的关系。比如联通块，种类等等。
除了一般的并查集之外，还有种类并查集，关系并查集，带权并查集等等。
如果按秩合并(把小的并到大的身上)，并查集的复杂度是一个奇怪的函数，查找操作接近O(1),如果不按秩合并，复杂度大概是logN，还是很高效的。
但是似乎并查集本身并不能出很多题，所以这种数据结构经常和其它算法共同使用。
最基本的并查集
POJ 1611
题意：有n个人，他们组成了k个小组，小组之间的人接触比较密切。现在0号得了传染病，而只要是得了病的人都有可能传给各自所在小组内的人，问现在有可能多少人被传染了。
说了半天其实是个联通块问题，问有多少节点与0联通。然后我就懒得写了。。。
下面是我今年6月参加自主招生前复习时写的：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=50000; int f[N],n,m,ans; int get(int x) { if(f[x]!=x)f[x]=get(f[x]); return f[x]; } void init() {for(int i=1;i<=n;i++)f[i]=i;ans=0;} int main() { while(1) { scanf("%d%d",&n,&m); if(n==0&&m==0)break; init(); for(int i=1;i<=m;i++) { int x;scanf("%d",&x);int p,q; scanf("%d",&q);q++; for(int j=2;j<=x;j++) { scanf("%d",&p);p++; f[get(q)]=get(p);q=p; } } for(int i=1;i<=n;i++) if(get(i)==get(1))ans++; printf("%d\n",ans); } }
然后我还有一份我2015年寒假，也就是刚刚开始学oi时候写的代码。
从这两份代码中能看出代码风格的变化233333
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int n,k,w,ans=0; int s[30005]; int m[30005]; int getp(int x){if(x!=s[x])s[x]=getp(s[x]);return s[x];} void uset(int x,int y) { if((x=getp(x))==(y=getp(y)))return; s[x]=y; } int main() { while(1) { scanf("%d%d",&n,&k); for(int i=0;i<=n;i++)s[i]=i,m[i]=0; if(n==0&&k==0)break; for(int i=0;i<k;i++) { scanf("%d",&w); for(int j=0;j<w;j++) { scanf("%d",&m[j]); } for(int j=1;j<w;j++) { uset(m[j-1],m[j]); } } for(int i=0;i<=n;i++) { if(getp(i)==getp(0))ans++; } cout<<ans<<endl; ans=0; } return 0; }
很有意思，可惜我在2015年1月并不知道后面会滚粗的那么惨。
从这个水题我们总结一下并查集的两个关键操作：
第一，并
并查集本质上是个森林，合并集合操作即为把森林中的两棵树合并起来。
合并时我们其实只需要对根节点操作即可，然后随便选取一个新的根节点。
将A与B合并，其中A,B均为根节点，我们选取B为新的根节点，写成代码就是：fa[A]=B;这里其实以谁为根节点都无所谓，因为没有上下级关系。但是这个根结点的选取在带权并查集中有一些影响。
第二，查
查询时有一个重要的事是路径压缩，用递归实现。int get(int x) { if(x==fa[x])return fa[x]; fa[x]=find(fa[x]); return fa[x]; }递归到底，然后将下面的一点一点指向根节点。
记住，在递归到底之前做什么操作都是不对的！带权并查集血的教训！
扩展域并查集
poj 1182 食物链
经典中文题，题干略。
考虑每种生物和别的生物的关系，有同类，吃，或者被吃三种关系，所以我们建立三个域，同类域，吃域，被吃域。
然后考虑合并两种生物，以及产生的矛盾。
如果两种生物是同类，那么只需要把对应域合起来就行了。
最简矛盾情况：A的同类域是B的吃域或被吃域。
如果A吃B，那么只要把A的同类域并到B的被吃域，吃域并到B的同类域，被吃域并到B的吃域。
最简矛盾情况：A的同类域是B的同类域，A的同类域是B的吃域。
然后顺序做就行了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N=50005; int fa[N*3],n,cnt;//同 吃 被 int get(int x) { if(x!=fa[x])fa[x]=get(fa[x]); return fa[x]; } int uni(int a,int b) { int at=get(a),ac=get(n+a),ab=get(2*n+a); int bt=get(b),bc=get(n+b),bb=get(2*n+b); if(at==bc||at==bb)return 1; fa[at]=bt,fa[ac]=bc,fa[ab]=bb; return 0; } int eat(int a,int b)//a eat b { int at=get(a),ac=get(n+a),ab=get(2*n+a); int bt=get(b),bc=get(n+b),bb=get(2*n+b); if(at==bt||at==bc)return 1; fa[at]=bb,fa[ac]=bt,fa[ab]=bc; return 0; } int main() { scanf("%d%d",&n,&cnt); int ans=0; for(int i=1;i<=3*n;i++)fa[i]=i; while(cnt--) { int d,x,y; scanf("%d%d%d",&d,&x,&y); if(x>n||y>n){ans++;continue;} if(d==1)ans+=uni(x,y); else ans+=eat(x,y); } printf("%d\n",ans); }
一道类似的题：poj 2912
一群人玩石头剪刀布，每个人只会出固定的石头，剪刀或者布。但是有个人是裁判，他可以随便出。给出他们之间猜拳的胜败关系，要求找出裁判，并且输出最少找多少行。如果可能有多个裁判，输出”不可确定”，如果是不合法情况，输出”矛盾”。
数据范围很小，枚举裁判，删去当前枚举的人，用食物链的方式检验是否出现矛盾，如果没矛盾，枚举的这个人就有可能是裁判。如果不成立，记录出错的行数，所有出错行数取max为找到裁判的最少行数（因为至少要找到这一行才能排除其它所有人是裁判的可能性）。如果所有的都是矛盾，则输出”矛盾”，如果有两个及以上裁判，输出”不可确定”。
这里面吃域，同类域，被吃域变成了赢域，平域，输域。
注意细节啊！
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=505,M=2005; int fa[N*3+10],m,n; int p1[M],p2[M],p[M]; int get(int x) { if(x==fa[x]){return fa[x];} fa[x]=get(fa[x]); } void uni(int a,int b) { int x=get(a),y=get(b); if(x==y)return; fa[x]=y; } int work(int del) { for(int i=1;i<=3*n+2;i++)fa[i]=i; for(int i=1;i<=m;i++) { if(p1[i]==del||p2[i]==del)continue; int a=p1[i],b=p2[i]; // cout<<"d "<<del<<" "<<a<<" "<<b<<endl; if(p[i]==1) { int a1=get(a),a2=get(a+n),a3=get(a+2*n); int b1=get(b),b2=get(b+n),b3=get(b+2*n); // cout<<a1<<" "<<a2<<" "<<a3<<" "<<b1<<" "<<b2<<" "<<b3<<endl; if(a1==b2||a1==b3||a2==b1||a2==b3||a3==b1||a3==b2)return i; uni(a1,b1),uni(a2,b2),uni(a3,b3); } else { if(p[i]==3)swap(a,b); int a1=get(a),a2=get(a+n),a3=get(a+2*n);//同类 win lose int b1=get(b),b2=get(b+n),b3=get(b+2*n); // cout<<a1<<" "<<a2<<" "<<a3<<" "<<b1<<" "<<b2<<" "<<b3<<endl; if(a1==b1||a1==b2||a2==b2||a2==b3||a3==b1||a3==b3)return i; uni(a1,b3),uni(a2,b1),uni(a3,b2); } } return -1; } inline void init() {for(int i=1;i<=n*3;i++)fa[i]=i;} void debug() { for(int i=1;i<=m;i++) cout<<p1[i]<<" "<<p2[i]<<" "<<p[i]<<endl; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(m==0) { if(n==1)puts("Player 0 can be determined to be the judge after 0 lines"); else puts("Can not determine"); continue; } memset(p1,0,sizeof p1); memset(p2,0,sizeof p2); memset(p,0,sizeof p); for(int i=1;i<=m;i++) { char s[20]; scanf("%s",s); int len=strlen(s);int q=0,now=1; for(int j=0;j<len;j++) { if(s[j]=='='||s[j]=='<'||s[j]=='>') { q=j; if(s[j]=='=')p[i]=1; else if(s[j]=='>')p[i]=2; else p[i]=3; } } for(int j=q-1;j>=0;j--) { p1[i]+=(s[j]-'0')*now; now*=10; } now=1; for(int j=len-1;j>q;j--) { p2[i]+=(s[j]-'0')*now; now*=10; } p1[i]++,p2[i]++; } // debug(); int ans=0,flag=0; for(int i=1;i<=n;i++) { int t=work(i); // cout<<t<<endl; if(t<0) { if(flag>0)//多解 {puts("Can not determine");flag=-1;break;} flag=i; } else ans=max(ans,t); } if(flag==-1)continue; else if(flag==0){puts("Impossible");continue;} else printf("Player %d can be determined to be the judge after %d lines\n",--flag,ans); } }
另一种扩展域并查集（关系并查集）
poj1703
有两个帮派，现在给出两种操作，A a b：告知你ab为相同帮派，D a b查询ab是否属于同一帮派。
我们可以用一般的扩展域做，设两个域：同类域和不同域，合并的时候，如果是同类，那就相应的域合并，否则就反着合并，查询时如果同类域指向不同域，就是不同帮派。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; int fa[100005*2+5]; int find(int x){if(x!=fa[x])fa[x]=find(fa[x]);return fa[x];} void add(int x,int y) { if((x=find(x))==(y=find(y)))return; fa[x]=y;//把x并到y } int n,t,q; int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&q); for(int i=0;i<=n+100005;i++)fa[i]=i; while(q--) { char s[5]; int a,b; scanf("%s%d%d",s,&a,&b); if(s[0]=='D') { add(a,b+100005); add(a+100005,b); } else { if(find(a)==find(b))printf("In the same gang.\n"); else if(find(a)==find(b+100005)||find(a+100005)==find(b))printf("In different gangs.\n"); else {printf("Not sure yet.\n");} } } } return 0; }
也可以用另一种方法，关系并查集：
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int N=100015; int fa[N],s[N],n,m; int get(int x) { if(x==fa[x])return x; int t=fa[x]; fa[x]=get(fa[x]); s[x]^=s[t]; return fa[x]; } void uni(int a,int b,int t) { int x=get(a),y=get(b); if(x==y)return; //不需要if(x==y) fa[y]=x; s[y]=s[a]^s[b]^t; } int query(int a,int b) { int x=get(a),y=get(b); if(x!=y)return -1; //0 相同 1 不同 return s[a]^s[b]; } int main() { int cnt=0; scanf("%d",&cnt); while(cnt--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)fa[i]=i,s[i]=0; for(int i=1;i<=m;i++) { char ss[10];int a,b; scanf("%s%d%d",ss,&a,&b); if(ss[0]=='D')uni(a,b,1); else { if(n==2) { if(a!=b) puts("In different gangs."); else puts("In the same gang."); continue; }//特判 int t=query(a,b); if(t<0)puts("Not sure yet."); else puts(t?"In different gangs.":"In the same gang."); } } } return 0; }
s[x]表示自己与根结点的关系，s[x]=0代表同类，s[x]=1代表异类。
s[x]初始值为s[x]=0 自己与自己为同类
路径压缩时，s[x]=s[x]^s[fa[x]] 其中，fa[x]是s[x]直系亲属，而不是路径压缩后那个根，而且，注意在递归结束返回时进行这个操作！具体为啥，自己想！！！
合并时，s[new_root]=s[a]^s[b]^t，如果同类，t=0，异类，t=1。
这个没有扩展域好写。。但是写了之后莫名喜欢。。。。
poj1733
有一个长度已知的01串，给出[l,r]这个区间中的1是奇数个还是偶数个，给出一系列语句问前几个是正确的。
把[l,r]区间中的1的个数表示为sum[r]-sum[l-1]，如果sum[r]-sum[l-1]是偶数，说明sum[r]和sum[l-1]的奇偶性相同，否则奇偶性不同，这样又变成了是否相同集合的问题，可以用扩展域或者关系并查集来做。注意离散化！
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=20000; int fa[N],d[N],m,n,ans; int seq[N],cnt,ll[N],rr[N]; int opt[N]; int get(int x) { if(fa[x]==x)return x; int t=fa[x]; fa[x]=get(fa[x]); d[x]=d[x]^d[t]; return fa[x]; } bool add(int a,int b,int c) { int x=get(a),y=get(b); if(x==y) { if(d[a]==d[b]&&c==1)//1 为不同 return 0; if(d[a]!=d[b]&&c==0)//0 为相同 return 0; return 1; } fa[y]=x; d[y]=d[a]^d[b]^c; return 1; } int main() { while(scanf("%d%d",&m,&n)!=EOF) { cnt=ans=0; for(int i=1;i<=n;i++) { int l,r;char s[10]; scanf("%d%d%s",&l,&r,s); l--; seq[++cnt]=l,seq[++cnt]=r; ll[i]=l,rr[i]=r; opt[i]=(s[0]=='o'); } sort(seq+1,seq+cnt+1); for(int i=0;i<=cnt+5;i++)fa[i]=i,d[i]=0; for(int i=1;i<=n;i++) { int l,r; l=lower_bound(seq+1,seq+cnt+1,ll[i])-seq; r=lower_bound(seq+1,seq+cnt+1,rr[i])-seq; if(!add(l,r,opt[i]))break; ans++; } printf("%d\n",ans); } return 0; }
poj 1417
给出p1+p2个人，其中p1个是好人，p2个是坏人。然后有一些关系 ，a说b是好人(坏人).其中没有矛盾的，判断是否有唯一解判断哪些人是好人，哪些人是坏人。
如果一个人说另一个人是好人，如果这个人是好人，那么另一个人是好人，如果这个人是坏人，那么另一个人是坏人。
如果一个人说另一个人是坏人，如果这个人是坏人，那么另一个人是好人，如果这个人是好人，那么另一个人是坏人。
可得 如果一个人说另一个是好人，那么这两个人属于同一集合，否则属于不同集合。
用并查集处理后，组成k棵树，对于每棵树处理，把好人和坏人挑出来，分别放在q[i][0]和q[i][1]中
i个集合，选了j个好人/坏人 （我们不知道选的是好人或者坏人，只有相对的两个集合）
f[i][j]=f[i-1][j-q[i][0]]+f[i-1][j-q[i][1]] （选好人或者坏人）
只需要看f[k][p1]或者f[k][p2]是否小于2就行，输出方案有点恶心。。。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int N=1005; int fa[N];int r[N]; int n,cnt,path[N][N]; int get(int x) { if(x==fa[x])return x; int t=fa[x]; fa[x]=get(fa[x]); r[x]^=r[t]; return fa[x]; } void uni(int a,int b,int x) { int aa=get(a); int bb=get(b); if(aa==bb)return; fa[bb]=aa; r[bb]=r[a]^r[b]^x; } int ans[N][3]; int q[N][3],a[N];//集合人数,集合编号 int f[N][N];//i个集合，选了j个好人 //f[i][j]=f[i-1][j-q[i][0]]+f[i-1][j-q[i][1]] //意思是假设这组人是好人或坏人 void init() { for(int i=1;i<=n;i++) if(get(i)==i)a[i]=++cnt;//新的一组集合 for(int i=1;i<=n;i++) { q[a[get(i)]][r[i]]++; } } void dp() { f[0][0]=1;//0组集合 0人 方案数为1 for(int i=1;i<=cnt;i++) for(int j=0;j<=n;j++) { if(j-q[i][0]>=0&&f[i-1][j-q[i][0]]>0) { f[i][j]+=f[i-1][j-q[i][0]]; path[i][j]=q[i][0]; } if(j-q[i][1]>=0&&f[i-1][j-q[i][1]]>0) { f[i][j]+=f[i-1][j-q[i][1]]; path[i][j]=q[i][1]; } if(f[i][j]>1)f[i][j]=2; } } int main() { int t,p1,p2; while(scanf("%d%d%d",&t,&p1,&p2)!=EOF) { if(t==0&&p1==0&&p2==0)return 0; for(int i=1;i<=p1+p2;i++)fa[i]=i; memset(r,0,sizeof r); memset(f,0,sizeof f); memset(path,0,sizeof path); memset(q,0,sizeof q); memset(a,0,sizeof a); memset(r,0,sizeof r); memset(ans,0,sizeof ans); cnt=0; n=p1+p2; for(int i=1;i<=t;i++) { char c[10];int a,b; scanf("%d%d%s",&a,&b,c); uni(a,b,c[0]=='n'); } init(); dp(); if(f[cnt][p1]!=1)puts("no"); else { for(int i=cnt,j=p1;i>0&&j>0;i--) { if(q[i][0]==path[i][j])ans[i][0]=1; else ans[i][1]=1; j-=path[i][j]; } for(int i=1;i<=n;i++) if(ans[a[get(i)]][r[i]])printf("%d\n",i); printf("end\n"); } } }
带权并查集
把每个节点加上一个到根结点的距离，就可以叫带权并查集了。在路径压缩的时候记着把路径都加上。合并的时候要具体情况具体分析。
poj1984
给出一个地图（只有四个方向上的距离），询问任意两点间曼哈顿距离。
带权并查集记录上和右的距离，合并时合并根节点，并直接算出到旧根到新根的距离，更新权值。
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int N=100000; int fa[N],rd[N],dd[N];//right dist down dist int a[N],b[N],r[N],d[N],tot,n,m; void add(int aa,int bb,int cc,int dd) { tot++; a[tot]=aa,b[tot]=bb,r[tot]=cc,d[tot]=dd; } struct seq { int a,b,c,ans,k; }q[10005]; bool cmp(seq t1,seq t2) {return t1.c<t2.c;} bool cmp2(seq t1,seq t2) {return t1.k<t2.k;} int get(int x) { if(x==fa[x])return x; int t=fa[x]; fa[x]=get(fa[x]); // cout<<"get "<<rd[t]<<" "<<dd[t]<<endl; rd[x]+=rd[t]; dd[x]+=dd[t]; return fa[x]; } void uni(int a,int b,int r,int d) { //cout<<"uni "<<a<<" "<<b<<" "<<r<<" "<<d<<endl; int x=get(a),y=get(b); if(x==y)return; fa[y]=x; rd[y]=rd[a]-rd[b]+r; dd[y]=dd[a]-dd[b]+d; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { fa[i]=i; } for(int i=1;i<=m;i++) { char s[10]; int aa,bb,cc; scanf("%d%d%d%s",&aa,&bb,&cc,s); // 'N''E''S' 'W' if(s[0]=='N')//a向北走c到b add(aa,bb,0,-cc); else if(s[0]=='E')//a向东走c到b add(aa,bb,cc,0); else if(s[0]=='S') add(aa,bb,0,cc); else//west 西 add(aa,bb,-cc,0); } int cnt=0; scanf("%d",&cnt); for(int i=1;i<=cnt;i++) scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].c),q[i].k=i; sort(q+1,q+cnt+1,cmp); int now=0; for(int i=1;i<=cnt;i++) { // cout<<now<<endl; if(now<q[i].c) { for(int j=now+1;j<=q[i].c;j++) uni(a[j],b[j],r[j],d[j]),now=j; } // cout<<q[i].a<<" "<<q[i].b<<endl; int x=get(q[i].a),y=get(q[i].b); // cout<<x<<" tt "<<y<<" "<<q[i].a<<" "<<q[i].b<<endl; // cout<<x<<" x "<<y<<endl; if(x!=y)q[i].ans=-1; else { // cout<<rd[q[i].a]<<" "<<rd[q[i].b]<<" "<<dd[q[i].a]<<" "<<dd[q[i].b]<<endl; q[i].ans=abs(rd[q[i].a]-rd[q[i].b])+abs(dd[q[i].a]-dd[q[i].b]); } } sort(q+1,q+1+cnt,cmp2); for(int i=1;i<=cnt;i++)printf("%d\n",q[i].ans); return 0; }
全文完。。。