并查集是一种树型的数据结构。注意这棵树的形态是不固定的，只要所有点的根节点都相同即可。
1 int getfather(int x){ 2 if(fa[x]==x) return x; 3 return fa[x]=getfather(fa[x]); 4 } 5 void merge(int x,int y){ 6 x=getfather(x); 7 y=getfather(y); 8 //if(rank[x]<rank[y]) swap(x,y); 9 fa[y]=x; 10 //if(rank[x]==rank[y]) ++rank[x]; 11 }
路径压缩 【O(nlogn)】 +按秩合并 【树深<=O(logn)】 = 【O(n α(n))】 。
（一） [HAOI2006]旅行
题意 ：有一个 n 个点，m 条边的图，求一条从 s 到 t 的路径，使得 最大值与最小值的比值最小。
范围 ： n ≤ 500, m ≤ 5000
思路 ：枚举最小边，然后加入比它大的边直到 s 和 t 连通为止。用并查集来支持加入一条边，查询 s,t 是否连 通，时间复杂度 O(m2α(n))。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #define M 5050 6 using namespace std; 7 int n,m,s,t,ansx=0,ansy=0,fa[M]; 8 double ans1[M],ans2[M],minn=99999999; 9 int read(){ 10 int x=0; 11 char a=getchar(); 12 while(a<‘0‘||a>‘9‘) a=getchar(); 13 while(a>=‘0‘&&a<=‘9‘){ 14 x=x*10+a-‘0‘; 15 a=getchar(); 16 } 17 return x; 18 } 19 double min(double x,double y){ // 手写 double min 20 return (x<y)?x:y; 21 } 22 struct ss{ 23 int x,y,v; 24 }f[M]; 25 bool cmp(ss a,ss b){ 26 return a.v<b.v; 27 } 28 int getfather(int x){ //查询 29 if(fa[x]==x) return x; 30 return fa[x]=getfather(fa[x]); 31 } 32 void merge(int x,int y){ // 合并 33 x=getfather(x); 34 y=getfather(y); 35 fa[x]=y; 36 } 37 int main() 38 { 39 memset(ans1,-1,sizeof(ans1)); 40 memset(ans2,-1,sizeof(ans2)); 41 n=read(),m=read(); 42 for(int i=1;i<=m;i++) 43 f[i].x=read(),f[i].y=read(),f[i].v=read(); 44 s=read(),t=read(); 45 sort(f+1,f+1+m,cmp); 46 47 for(int i=1;i<=m;i++){ 48 for(int k=1;k<=n;k++) fa[k]=k; 49 for(int j=i;j<=m;j++){ 50 merge(f[j].x,f[j].y); 51 if(getfather(s)==getfather(t)){; //查询s, t是否在一个集合内 52 ans1[i]=f[i].v,ans2[i]=f[j].v;break; 53 } 54 } 55 } 56 for(int i=1;i<=m;i++){ 57 if(ans1[i]==-1) continue; 58 double k=ans2[i]/ans1[i]; 59 if(k<minn){ 60 ansx=(int)ans1[i],ansy=(int)ans2[i]; 61 minn=k; 62 } 63 } 64 if(ansx==0&&ansy==0) printf("IMPOSSIBLE"); 65 else if(ansy%ansx==0) printf("%d",ansy/ansx); 66 else { 67 for(int i=2;i<ansx;i++){ 68 if(ansx%i==0&&ansy%i==0) ansx/=i,ansy/=i; 69 } 70 printf("%d/%d",ansy,ansx); 71 } 72 return 0; 73 }
（二）P1525 关押罪犯
题意： 有 n 个罪犯，m 个事件，2 个监狱。每个事件有三个数 ai , bi , ci，表示若 ai , bi 号犯人关在一起，则会产生 ci 的影响力。 现在你需要合理分配罪犯到两个监狱，使得所有发生的事件 中最大的 ci 尽可能小。
范围： n ≤ 1e4 , m ≤ 1e5
思路：贪心+并查集
1 #include<cstdio> 2 #include<algorithm> 3 #define N 100010 //1.开小(开成n的取值) 4 using namespace std; 5 int n,m,x,y,fa[N]; 6 struct node 7 { 8 int a,b,c; 9 }e[N]; 10 bool cmp(node x,node y) 11 { 12 return x.c>y.c; 13 } 14 int find(int k) 15 { 16 if(k==fa[k]) return k; 17 return fa[k]=find(fa[k]); 18 } 19 int main() 20 { 21 scanf("%d%d",&n,&m); 22 for(int i=1;i<=m;i++) 23 scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c); 24 sort(e+1,e+1+m,cmp); 25 for(int i=1;i<=n*2;i++) fa[i]=i; // 后面拆点（1->2） 26 for(int i=1;i<=m;i++) 27 { 28 x=find(e[i].a); 29 y=find(e[i].b); 30 if(x==y){ 31 printf("%d",e[i].c); 32 return 0; 33 } 34 fa[x]=find(e[i].b+n); //2.不用find会超时 (空?MLE) 35 fa[y]=find(e[i].a+n); //拆点 36 } 37 printf("0"); 38 return 0; 39 }
（三） 种类并查集
题意 ：给定 n 个条件形如 a 与 b 是朋友或者 a 与 b 是敌人。满足 我朋友的朋友是我的朋友，我敌人的敌人是我的朋友。所有 朋友组成一个团伙，问一共有多少团伙。
范围 ：n ≤ 1e5
1 #include<cstdio> 2 #include<iostream> 3 const int N=1000*2+10; 4 using namespace std; 5 //FILE *fin=fopen("gangs.in","r"); 加文件RE 6 //FILE *fout=fopen("gangs.out","w"); 7 char a; 8 int n,m,fa[N],vis[N],ans; 9 int getfather(int x){ 10 if(fa[x]==x) return x; 11 return fa[x]=getfather(fa[x]); 12 } 13 void merge(int x,int y){ 14 x=getfather(x); 15 y=getfather(y); 16 fa[x]=y; 17 } 18 int main() 19 { 20 scanf("%d%d",&n,&m); 21 for(int i=1;i<=n*2;i++) fa[i]=i;//fa[i]朋友，fa[i+n]敌人 22 while(m--){ 23 cin>>a; 24 int x,y; 25 if(a==‘F‘){ 26 scanf("%d%d",&x,&y); 27 merge(x,y);//注意：不需要 merge(x+n,y+n); 朋友的敌人 与 朋友的敌人 不是朋友!!! 28 } 29 else { 30 scanf("%d%d",&x,&y); 31 merge(x+n,y),merge(x,y+n); 32 } 33 } 34 for(int i=1;i<=n;i++){ 35 int x=getfather(i); 36 if(!vis[x]){ 37 ans++; 38 vis[x]=1; 39 } 40 } 41 printf("%d",ans); 42 return 0; 43 }
(2) P2024 [NOI2001]食物链
题意 :有三类动物 A, B, C，这三类动物的食物链构成环。
A 吃 B，B 吃 C，C 吃 A。现有 n 个动物，以 1 ∼ n 编号。每个动物都 是 A,B,C 的一种，但是我们并不知道它到底是哪一种。 现在有 k 个条件，每个条件形如： 1 x 吃 y 2 x 和 y 是同类 现在让你依次判断 k 个条件的真假，一个条件是真的，当且 仅当其不与题设条件以及之前的真条件冲突，你需要输出假条件的总数。
范围 : n ≤ 5 ∗ 1e4 , m ≤ 1e5
思路：与上题类似，把 x 拆为三个点 x1, x2, x3，若 x 与 y 是同类， 那么 x1, y1， x2, y2， x3, y3 是同类。假设 x 吃 y，那么 x2, y1， x3, y2， x1, y3 是同类。只需要判断是否出现矛盾即可。
1 #include<cstdio> 2 using namespace std; 3 int n,k,fa[300010],x,y,z,ans; 4 int find(int a) 5 { 6 if(fa[a]==a) return a; 7 return fa[a]=find(fa[a]); 8 } 9 //查 10 void get(int a,int b) 11 { 12 int v=find(a),u=find(b); 13 fa[v]=u; 14 } 15 //并 16 int main() 17 { 18 scanf("%d%d",&n,&k); 19 for(int i=1;i<=n*3;i++) fa[i]=i;//初始化 20 21 ans=0; 22 for(int i=1;i<=k;i++) 23 { 24 scanf("%d%d%d",&x,&y,&z); 25 if(y>n||z>n){ans++; continue;}//特判一 当前的话中 y 或 z 比 N 大，就是假话 26 if(x==1)//判断同类 27 { 28 if(find(y+n)==find(z)||find(y+2*n)==find(z))//z是否为y的天敌或猎物 29 {ans++; continue;} 30 get(y,z),get(y+n,z+n),get(y+2*n,z+2*n);//建立y与z同类、y的天敌是z的天敌、y的猎物是z的猎物的3种关系 31 } 32 else if(x==2)//判断y是z的天敌 33 { 34 if(y==z){ans++; continue;}//特判二 当前的话表示自己吃自己，就是假话 35 if(find(y)==find(z)||find(y+n)==find(z))//z是否是 y同类 或 天敌 36 {ans++; continue;} 37 get(y+n*2,z),get(y+n,z+2*n),get(y,z+n);//建立y的猎物是z、y的天敌是z的猎物（环形）、z的猎物的天敌是y 的3种关系 38 } 39 } 40 printf("%d",ans); 41 return 0; 42 }
（四）SP5150 JMFILTER - Junk-Mail Filter
题意 ：n 次操作，支持：
• 合并 a, b。
• 将 a 从当前集合删去，放入一个新的集合。
求最后集合的个数。
范围 ：n ≤ 1e5
思路：删除 a 只需要新建一个节点来代表 a 即可，原来的节点同样 存在于并查集中，但是不代表 a。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 const int N=1e7; 5 using namespace std; 6 int rep[N],fa[N],vis[N],cnt,ans,T,n,m; 7 int getfather(int x){ 8 if(fa[x]==x) return x; 9 return fa[x]=getfather(fa[x]); 10 } 11 void merge(int x,int y){ 12 x=getfather(x); 13 y=getfather(y); 14 fa[x]=y; 15 } 16 int main() 17 { 18 scanf("%d%d",&n,&m); 19 while(n!=0||m!=0){ 20 //printf("111"); 21 T++; 22 ans=0; 23 cnt=n; 24 for(int i=0;i<n;i++) rep[i]=i; 25 for(int i=0;i<n+m;i++) fa[i]=i; 26 while(m--){ 27 char a; 28 int x,y; 29 cin>>a;//这里用cin啊啊啊!!!读入字符用cin!! 30 if(a==‘M‘){ 31 scanf("%d%d",&x,&y); 32 merge(rep[x],rep[y]); 33 } 34 else{ 35 scanf("%d",&x); 36 rep[x]=cnt++; //新建一个新节点代表x节点 37 } 38 //printf("%d%d%d\n",m,m,m); 39 } 40 memset(vis,0,sizeof(vis)); 41 for(int i=0;i<n;i++){ 42 int x=getfather(rep[i]); 43 if(!vis[x]){ 44 ans++; 45 vis[x]=1; 46 } 47 } 48 printf("Case #%d: %d\n",T,ans); 49 scanf("%d%d",&n,&m); 50 } 51 return 0; 52 }
注：参考资料 郑州培训dzy老师课件
原文：https://www.cnblogs.com/RR-Jin/p/11330062.html