一、并查集的概念

并查集(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操作优化可以判断树高，使小树并到大树中
该方法构造的树高不超过 $\lfloor log_2n \rfloor +1$
优化后Find操作最坏时间复杂度为 $O(log_2n)$

并操作的时间复杂度为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;
}