ACM模板——并查集

 1 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 2 const int maxn = 50003;
 3 int par[maxn]; //父亲 
 4 int high[maxn]; //树的高度
 5 
 6 void init(int n)
 7 {
 8     _for(i,0,n)
 9     {
10         par[i] = i;
11         high[i] = 0;
12     }
13 } 
14 
15 int find(int x)
16 {
17     return par[x] == x ? par[x] = x : par[x] = find(par[x]);
18 }
19 
20 void unite(int x,int y)
21 {
22     x = find(x);y = find(y);
23     if(x==y) return ;
24     
25     if(high[x]<high[y])
26         par[x] = y;
27     else
28     {
29         par[y] = x;
30         if(high[x]==high[y])
31             high[x] ++;
32     }
33 }
34 
35 bool same(int x,int y)
36 {
37     return find(x) == find(y); 
38 }