一、 并查集的概念
并查集(Disjoint Set)的逻辑结构属于集合，只进行并和查两种基本操作。一个集合可以划分为若干个互不相交的子集，在集合这种逻辑关系之间，两个元素要么处于同一集合，要么属于不同集合。
image
回顾森林的概念：森林上m个互不相交的树，实际上就是多个集合
并查集的数据结构可以简单的定义为一纬数组，实际上就是森林的双亲表示法。
image
基于以上数据结构，并查集的基本操作有
"查操作"：确定一个指定元素所属的集合——找到其根节点
"并操作"：将两个不相交的集合合并为一个——将一个集合的根节点成为另外一个根的右孩子
#define Size 13
int UFSets[Size]; //集合元素数组
//初始化并查集
void Initial(int S[]){
for(int i=0;i<Size;i++)
S[i]=-1
}
//"查"操作，找x所属集合
int Find(int S[],int x){
while(S[x]>=0) //循环寻找x的根
x=S[x];
return x; //根的S小于0
}
//并操作，将两个集合合并为一个
void Union(int S[],int Root1, int Root2){
if (Root1==Root2) return;
S[Root2]=Root1; //将根Root2链接到另外一个根的下面
}
查操作最坏(树高h=n)的时间复杂度为O(n)
对Union操作优化可以判断树高，使小树并到大树中
该方法构造的树高不超过
优化后Find操作最坏时间复杂度为
并操作的时间复杂度为O(1)
二、 并查集的应用
判断图的连通分量数：遍历各条边，有边相连的两个顶点一定是连通的，将两个顶点所属集合合并为一个集合。处理完所有边，即可将图划分为若干个连通分量
image
int ComponentCount(int g[5][5]){
//g[5][5]是二维数组表示的邻接矩阵
int S[5];
for (int i=0;i<5;i++) S[i]=-1;
//遍历各条边，数组是上三角矩阵，只需便利部分即可
for(int i=0;i<5;i++)
for(int j=i+1;j<5;j++)
if(g[i][j]>0){
int iRoot = Find(S,i); //找到i所属集合
int jRoot = Find(S,j); //找到j所属集合
if(iRoot!=jRoot) //i、j并入同一集合
Union(S,iRoot,jRoot);
}
//统计有几个连通分量
int count=0;
for(int i=0;i<5;i++)
if(S[i]<0) count ++;
return count;
}
