并查集

 1 int pre[1010]; //存放第i个元素的父节点
 2  
 3 int Find(int root) //查找根结点
 4 {
 5     int son, tmp;
 6     son = root;
 7     while(root != pre[root]) //寻找根结点
 8         root = pre[root];
 9     while(son != root) //路径压缩
10     {
11         tmp = pre[son];
12         pre[son] = root;
13         son = tmp;
14     }
15     return root;
16 }
17  
18 void Union(int root1, int root2) //判断是否连通，不连通就合并
19 {
20     int x, y;
21     x = unionsearch(root1);
22     y = unionsearch(root2);
23     if(x != y) //如果不连通，就把它们所在的连通分支合并
24         pre[x] = y;
25 }