（Disjoint Sets）的合并及查询问题。
有一个联合-查找算法（union-find algorithm）定义了两个操作用于此数据结构：
Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。Union：将两个子集合并成同一个集合。
下面代码实现一些并查集中的一些基本操作：
一、并查集的初始化
假设现在有一个全集合为S= {0,1,2,3,4,5,6,7,8,9} ，初始化时，将每一元素都划分成为一个单元素的集合。
如下图所示：
这样就初始化出10个单元素集合，每一个集合元素的parent值都是-1.
代码实现过程：
int parent[100];//构造一个初始并查集，s是集合元素的个数，此时初始化了s个集合，每一个集合都只有一个元素//数组的范围为parent[0]~parent[s-1]//初始的时候，数组元素的值都是 -1，表示此时都是根结点。void ufset(int s){int si=s;for(int i=0;i<si;i++)parent[i]=-1;}二、合并Union
所谓合并，即是将两个不相交的集合合并成为一个集合，这个过程将一个集合的parent修改成另一集合的parent。
代码实现过程：
//集合的合并//让root2的父指针指向root1即可实现两个集合的合并void Union(int root2,int root1){parent[root1]+=parent[root2];parent[root2]=root1;}
举个例子：初始化10个元素（如上图所示），进行下面的合并过程：
ufset(10); //初始化10个元素Union(6,0);Union(7,0);Union(8,0);Union(4,1);Union(9,1);Union(3,2);Union(5,2);
合并之后的结果：
但是进行这种合并之后，可能会出现一种不好的效果。如下图：
我们称之为一棵退化的树。
那么如何进行改进呢？我们可以使用加权规则进行合并。也就是将集合元素少的归到集合元素多的中去。
例如：
下面给出代码实现：（注意下面这个方法存在错误，请看下面第二个方法，已修正错误。）
//使用加权规则得到改进的Union操作void WeightUnion(int root2,int root1){int r2=Find(root2); //r2和r1是root2和root1的父结点int r1=Find(root1);int temp;if(r1!=r2){temp=parent[r1]+parent[r2];if(parent[r1]<parent[r2]){parent[r1]=temp;parent[r2]=r1;} //以r2根的树结点多else {parent[r1]=r2;parent[r2]=temp;}}}
错误提醒：很感谢某位网友指出我上面段代码的错误，由于一时疏忽上面WeightUnion这个方法有点错误！修改如下：
//使用加权规则得到改进的Union操作void WeightUnion(int root2,int root1){int r2=Find(root2); //r2和r1是root2和root1的父结点int r1=Find(root1);int temp;temp=parent[r1]+parent[r2];if(parent[r1]<=parent[r2])//注意：parent[r1] 和 parent[r2] 都是负数，所以小者其绝对值大，那么拥有的结点数就多//这里就说明 r1为根的树结点 不少于 r2为根的树结点{parent[r1]=temp; //以r1为根parent[r2]=r1;}else{parent[r1]=r2;parent[r2]=temp;}}
三、查找Find
我们知道，只有当查找到的元素的parent值为负数（此时集合元素个数用这个负数表示），才表示找到根。
//查找元素x所在集合//从x开始，沿父指针链一直向上，直到向上，直到达到一个父指针域为负值的结点位置int Find(int x) //迭代查找方式{while(parent[x]>=0) x=parent[x];return x;}/*int find_1(int x) //递归查找方式{if(parent[x]<0) return x; //x是根时，直接返回xelse return find_1(parent[x]); //否则，递归找x的父的根}*/进一步优化，，在查找过程中可以采用折叠规则压缩路径。
实现的代码：
//折叠规则压缩路径法//包含元素i的树中搜索根，并将从元素i到根的路径上的所有结点都变成根的结点int collapsingfind(int i){int j;for(j=i;parent[j]>=0;j=parent[j]); //搜索j的根while(i!=j) //向上逐次压缩{int temp=parent[i];parent[i]=j;i=temp;}return j; //返回根}
附：上面代码的完整版：
切忌贪婪，恨不得一次玩遍所有传说中的好景点，
