并查集模板

 1 #define MAX ****   //自己设置最大值
 2  
 3 // father[x]表示x的父节点
 4 int father[MAX];
 5 // rank[x]表示x的秩
 6 int rank[MAX];
 7  
 8 // 初始化
 9 void Make_Set(int n)
10 {
11     for(int i=1; i<=n; ++i)
12     {
13         father[i] = i;
14         rank[i] = 0;
15     }
16 }
17  
18 // 查找
19 int Find_Set(int x)
20 {
21     if(x != father[x])
22         return Find_Set(father[x]);
23     return x;
24 }
25  
26 // 合并
27 void Union(int x, int y)
28 {
29     x = Find_Set(x);
30     y = Find_Set(y);
31     if(x == y)  // x,y在同一个集合
32         return;
33     if(rank[x] > rank[y])
34         father[y] = x;
35     else if(rank[x] < rank[y])
36         father[x] = y;
37     else
38     {
39         rank[y]++;
40         father[x] = y;
41     }
42 }
转自：wutianqi http://www.wutianqi.com/?p=1066