所谓集合的并查主要是指两种运算，并（把两个集合并在一起）和查（查找某个元素是属于什么集合的），这里有一个经典题目
例子：有10台电脑{1,2,3,...,9,10}，已知下列电脑之间已经实现了连接：
1和2,2和4,3和5,4和7,5和8,6和9,6和10
问：2和7之间，5和9之间是否是联通的？
解决思路：
（1）将10台电脑看成10个集合{1},{2},{3},...,{9},{10}
（2）已知一种连接“x和y”，就将x和y对应的集合合并；
（3）查询“x和y是否是连通的”就是判别x和y是否属于同一集合
有一种方法是用集合中的某个元素作为树根，其他元素作为叶子结点，例如
并的时候只要把其根挂在另一个根下就好，这种表示方法叫做双亲表示法，也就是孩子指向其父亲
两个函数分别为
//查找某个元素所在的集合（用根节点表示） int Find(SetType S[],ElementType X){ //在数组S中查找值为X的元素所属的集合 //MaxSize是全局变量，为数组S的最大长度 int i; for(i=0;i<MaxSize&&S[i].Data!=X;i++); if(i>=MaxSize) return -1;//未找到X，返回-1 for(;S[i].Parent>=0;i=S[i].Parent); return i; }; //集合的并运算 void Union(SetType S[],ElementType X1,ElementType X2){ int Root1,Root2; Root1=Find(S,X1); Root2=Find(S,X2); if(Root1!=Root2)S[Root2].Parent=Root1; };下面对如下图所示的举例首先是查找结点10和3的根，然后将两个集合合并，再次找其根节点
执行结果是
附上完整代码
#include <stdio.h> #include <stdlib.h> #define MaxSize 100 typedef int ElementType; typedef struct{ ElementType Data; int Parent;//父节点的下标 }SetType; //查找某个元素所在的集合（用根节点表示） int Find(SetType S[],ElementType X); //集合的并运算 void Union(SetType S[],ElementType X1,ElementType X2); int main(){ SetType S[MaxSize]; int a[10]={1,2,3,4,5,6,7,8,9,10}; int b[10]={-1,0,-1,0,2,-1,0,2,5,5}; for(int i=0;i<MaxSize;i++){ S[i].Data=S[i].Parent=-1; } for(int i=0;i<10;i++){ S[i].Data=a[i]; S[i].Parent=b[i]; } printf("10在的根节点为%d\n",Find(S,10)+1); printf("3在的根节点为%d\n",Find(S,3)+1); printf("\n"); Union(S,10,3); printf("10在的根节点为%d\n",Find(S,10)+1); printf("3在的根节点为%d\n",Find(S,3)+1); system("pause"); } //查找某个元素所在的集合（用根节点表示） int Find(SetType S[],ElementType X){ //在数组S中查找值为X的元素所属的集合 //MaxSize是全局变量，为数组S的最大长度 int i; for(i=0;i<MaxSize&&S[i].Data!=X;i++); if(i>=MaxSize) return -1;//未找到X，返回-1 for(;S[i].Parent>=0;i=S[i].Parent); return i; }; //集合的并运算 void Union(SetType S[],ElementType X1,ElementType X2){ int Root1,Root2; Root1=Find(S,X1); Root2=Find(S,X2); if(Root1!=Root2)S[Root2].Parent=Root1; };这样做就是会出现一个问题，有可能会把高的树挂在低的树下面，树越来越大的同时也会越来越高，所以会导致Find效率会降低，为了改善合并以后的查找性能，可以采用小的集合合并到相对大的集合中，正好可以修改根节点原本的-1的值，表示其下面挂了几个元素，修改后的Union函数为 //集合的并运算 void Union(SetType S[],ElementType X1,ElementType X2){ int Root1,Root2; Root1=Find(S,X1); Root2=Find(S,X2); if(Root1!=Root2){ if(S[Root1].Parent<S[Root2].Parent){S[Root2].Parent=Root1;S[Root1].Parent+=S[Root2].Parent;} else {S[Root1].Parent=Root2;S[Root2].Parent+=S[Root1].Parent;} } };哈哈哈哈哈，done