2018年9月

并查集一般用于对动态连通性的判断,主要应用于判断两个不相交元素是否在同一个集合,两个点是否连通,变量名等同性以及间接好友的判断。同时并查集经常作为其他模板的一部分实现某些功能
并查集常用于的题型为判断某两个元素是否属于同一个集合,判断图是否连通或是否有环,或配合其他算法如最小生成树Kruskal,与DP共同使用等。

一般,并查集都会实现两种操作,就是查询函数,和链接函数。

普通并查集

类似于树,按照节点的方式来储存,理解并查集。其中的元素的储存,是由原始父节点为代表的树形结构。
每一个元素, 都是一个集合,其中的数值,指向 上层节点(父节点),由此方法我们可以推断,
只要两个节点所储存的最原始的父节点相同, 则两个点所代表的元素位于同一个集合。

路径压缩

为了进一步加快查找的速度,我们直接将新加入的节点,连接到原始节点上,这样就可以直接看出,两元素是否位于相同集合。

三个操作 (数组为例)

初始化操作

建立合适的储存方式,一般有结构体和数组两种,差别不大,功能是一样的。

基本的初始化,就是建立每一个节点的信息,比如 要储存当前元素的父节点,要储存当前元素在树内的深度,
当前元素所代表的数值意义等等。
有时可以将元素所代表的数值意义和当前元素的父节点合并表示,根据题目不同,还要建立别的,具体再分析。

#include <bits/stdc++.h>
const int maxn = 100000;

int m[maxn] = {0};
int r[maxn] = {0};// 数据比较多,节点链比较长时,合并短的,节约时间。

void init(int End)
{
    for(int i = 0;i < maxn && i <= End; i++)//初始化每一个节点都是父节点,深度为0
    {
        m[i] = i;
        r[m] = 0;
    }
    return;
}

查找操作

  • 普通并查集的基本查找代码比较简单,这里直接给出代码。


    int Find(int i)
    {
        if(m[i] == i)
            return i;
        else
            return m[i] = Find(m[i]);//路径压缩
    }
  • 补充循环+路径压缩的代码 2018-05-20
    int Find(int i)
    {
        int pi = i;
        while(pre[pi] != pi)
            pi = pre[pi]; // 找到根节点
        int si = i,j;
        while(si != pi)
        {
            j = pre[si]; // 记录当前节点的前导节点
            pre[si] = pi;// 当前节点的前导节点设置为根节点
            i = j;// 继续处理当前节点的前导节点的前导节点为根节点
        }
        return pi;
    }

合并操作

  • 先给出不考虑深度(单链长度) 的代码



void Union(int a,int b){ m[Find(b)] = Find(a); return; }

下面是考虑深度(单链长度) 的代码

    void Union(int i,int j)
    {
        i=Find(i);
        j=Find(j);
        if(i == j)
            return ;
        if(rank[i] > rank[j])
            set[j] = i;
        else
        {
            if(rank[i] == rank[j])
                rank[j]++;
            set[i] = j;
        }
    }