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;
        }
    }
  1. 1
  2. 2
  3. 3