并查集模板

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int maxn=500010;
 6 int a[maxn], n;
 7 int fa[maxn];
 8 int rank[maxn];
 9 
10 void init() {
11     for(int i=1;i<=n; i++) {
12         fa[i]=i;
13         rank[i]=0;
14     }
15     return ;
16 }
17 
18 int find(int z) {
19     if(fa[z]!=z) 
20         return fa[z]=find(fa[z]);
21     return fa[z];
22 }
23 
24 void unionn(int x,int y) {
25     x=find(x);
26     y=find(y);
27     if (x==y) return ;
28     if(rank[x]<rank[y]) {
29         fa[x]=y;
30     } 
31     else {
32         fa[y]=x;
33         if (rank[x]==rank[y])
34          rank[x]++;
35     }
36     return;
37 }