基本算法之并查集

 |   

并查集是一种用途广泛的数据结构,能够快速地处理集合的合并和查询问题,并且实现起来非常方便,在很多场合中都有着非常巧妙的应用。本文首先介绍并查集的定义、原理及具体实现,然后结合hihocoder以及poj上的题目做一些具体实践。

定义和原理

并查集(Union-Find Set)是一种树型的数据结构,其保持着用于处理一些不相交集合( Disjoint Sets )的合并及查询问题。有一个联合-查找算法( union-find algorithm )定义了两个操作用于此数据结构:

  • Find 确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
  • Union 将两个子集合并成同一个集合。

因为它支持这两种操作,一个不相交集也常被称为联合-查找数据结构(union-find data structure)或合并-查找集合(merge-find set)。其他的重要方法, MakeSet,用于建立单元素集合。有了这些方法,许多经典的划分问题可以被解决。

网络上有两篇帮助理解的博文,博主用通俗易懂的语言,图文并茂的方式将并查集生动形象得阐释了。特附上博文链接:

代码实现

  • 并查集的数据存储 $O(N)$

    1#define LENMAX 1000000
    2int father[LENMAX]
    

    `
    虽然并查集是树型的数据结构,但是实际的存储是用数组,就跟堆排序一样。

  • 并查集的初始化MakeSet

    1void MakeSet(){
    2    int i;
    3    for(i=0;i<LENMAX;i++){
    4        father[i]=i;
    5    }
    6}
    

    MakeSet是并查集的初始化函数,这里采用father[i]==i` 来判定该 i 是否是某个集合的代表。

  • 并查集的查找操作 $O(\alpha(N))[\alpha(N)<N]$

     1// 查找操作--未压缩路径
     2int Find(int x){
     3    if(x==father[x])
     4      return x;
     5    else
     6      return Find(father[x]);
     7}
     8
     9// 查找操作--压缩路径
    10int Find(int x){
    11    if(x==father[x])
    12      return x;
    13    else{
    14        father[x]=Find(father[x]);
    15        return father[x];
    16    }
    17}
    

    `
    压缩路径可以避免重复查找,其实际的意义是将树的深度由 n 变成 1 。就是将层层的等级制度变成全部向皇帝/代表负责。

  • 并查集的合并操作 $O(\alpha(N))[\alpha(N)<N]$

     1// 合并操作
     2void Union(int x, int y){
     3    int fatherX = Find(x);
     4    int fatherY = Find(y);
     5
     6    // fatherY归fatherX管了
     7    if(fatherX!=fatherY)
     8      father[fatherY]=fatherX;
     9
    10    /*
    11    // 合并的时候取小的数值
    12    if(fatherX<fatherY)
    13        father[fatherY]=fatherX;
    14    else
    15        father[fatherX]=fatherY;
    16    */
    17}
    

    `

解题报告

  • HihoCoder

    1. 第十四周: 无间道之并查集 | 源码

      注意点:

      1. 通过 map 将名称转化为 int 标号
      2. 最后一步判定两个名称是否是同一个集合时用 Find(mapName[nameX])==Find(mapName[nameY]) ,不能用father[mapName[nameX]]==father[mapName[nameY]]
  • POJ

    1. 1611: The Suspects | 源码

      注意点:

      1. 判定i是否和0同一类必须得通过Find找到最高的根节点是相同[代码实现可以添加rank[LENMAX]来记录同集合的元素个数]
    2. 2524: Ubiquitous Religions | 源码

      注意点:

      1. 通过 i=father[i] 判断是否是根节点,也就是说是否是一个集合

参考文献

  1. 维基百科之并查集
技术茶话会
< 前一篇 后一篇 >