并查集

1 概述                  

并查集常常用来判断在一个图中是否存在回路（是否可以生成树），以及用来判断图的联通性问题。

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

 

我们这里直接采用基于 Rank 合并（合并时将元素所在深度小的集合合并到元素所在深度大的集合）方式的实现。

 

并查集的数学模型是一组不相交的动态集合的集合S={A,B,C,...}，它支持以下的运算：

 在并查集中需要两个类型的参数：集合名字的类型和元素的类型。在许多情况下，可以用整数作为集合的名字。如果集合***有n个元素，可以用范围【1：n】以内的整数表示元素。实现并查集的一个简单方法是使用数组表示元素及其所属子集的关系。其中，用数组下标表示元素，用数组单元记录该元素所属的子集名字。如果元素类型不是整型，则可以先构造一个映射，将每个元素映射成一个整数。这种映射可以用散列表或其他方式实现。

2 实现并查集所需要的几个步骤：

并查集的实现思想

采用数结构实现并查集的基本思想是，每个集合用一棵树表示。树的结点用于存储集合中的元素名。每个树结点还存放一个指向其父结点的指针。数根结点处的元素代表该数所表示的集合。利用映射可以找到集合中所对应的数结点。

父亲数组是实现上述数结构的有效方法。

  1. 初始化元素

2. 实现元素与元素间的联合操作
3. 实现查找元素所在树的根节点
4. 解决一个问题，判定两个元素是否在同一棵树上（两个元素是否相互连接）

具体步骤

首先，需要两个数组——parent[] 与weight[] ，parent用来存放该节点的父节点，weight用来存放该节点有多少的子节点，也就是该节点的“重量”。

其次，需要一个整数nums来记录一共有多少个不相连的集合。

并查集有三个基本的方法：init() , find() , union() 。init()用来对数组进行初始化，find()用来查找对应节点的根节点，union()用来连接节点。

1，init() 初始化

初始化时，每个节点的父节点都是他自身。每个节点对应的重量均为1，nums为集合中节点的数量，代码如下：

void init()

{

    for(int i = 0 ; i < parent.length ; i ++)

    {

          parent[i] = i ;

          weight[i] = 1 ;       

    }

    nums = parent,length ;

}

2   find()查找对应节点的根节点

find() 在查找根节点时，一直比较节点与父节点是否相同，如果相同则说明该节点为根节点。

int find(int p)

{

　　while(parent[p] != p)

　　{

　　　　p = parent[p] ;

　　}

　　return p ;

}

3，union()连接两节点对应的父节点

union()在连接两个节点的父节点时，需要比较两个节点的父节点的“重量”，将重量较大的节点看作为父节点将其合并，每合并一次，对应的nums的数量就会减一。

public static void union(int p,int q,int[] nodes,int[] weight)
{
    int n = find(p,nodes) ;
    int m = find(q,nodes) ;
    if(n == m ) return ;          //两节点的父节点相同，说明已经连接
    if(weight[n] > weight[m])
    {
        nodes[m] = n ;
        weight[n] += weight[m] ;
        nums -- ;
    }
    else{
        nodes[n] = m ;
            weight[m] += weight[n] ;
        nums -- ;
    }
}   

注意：在创建parent与weight数组时，数组的大小常常为节点个数加一，因为元素的节点常常从1开始，所以，定义的数组从1开始计数更为方便。