并查集(union-find sets)主要是用来快速判断两个点是否属于同一个集合，以及判断图的连通性。
下面我们来看并查集的实现。 int pre[1000]; 这个数组，记录了每个大侠的上级是谁。大侠们从1或者0开始编号（依据题意而定），pre[15]=3就表示15号大侠的上级是3号大侠。如果一个人的上级就是他自己，那说明他就是掌门人了，查找到此为止。也有孤家寡人自成一派的，比如欧阳锋，那么他的上级就是他自己。每个人都只认自己的上级。比如胡青牛同学只知道自己的上级是杨左使。张无忌是谁？不认识！要想知道自己的掌门是谁，只能一级级查上去。
find这个函数就是找“上级”用的，意义再清楚不过了。
int Find(int x) // 查找x的"上级" { int r = x; // 委托r去找 while (r != pre[r]) //如果r的上级不是r自己 r = pre[r]; // r就接着找他的上级，直到找到老大为止。 int i = x, j; while(i != r) // 路径压缩 { j = pre[i]; pre[i] = r; i = j; } return r; } void Union(int x, int y) // 我想让虚竹和周芷若做朋友 { int fx = Find(x),fy = Find(y); // 虚竹的老大是玄慈，芷若MM的老大是灭绝 if(fx != fy) // 玄慈和灭绝显然不是同一个人 { pre[fy] = fx; // 方丈只好委委屈屈地当了师太的手下啦 } }转自：https://blog.csdn.net/u013546077/article/details/64509038
