乐趣区

关于算法:并查集详解及应用

jiezi

文章和代码曾经归档至【Github 仓库：https://github.com/timerring/algorithms-notes】或者公众号【AIShareLab】回复 算法笔记 也可获取。

并查集

1. 将两个汇合合并

2. 询问两个元素是否在一个汇合当中。

基本原理: 每个汇合用一棵树来示意。** 树根的编号就是整个汇合的编号。** 每个节点存储它的父节点，p[]示意 x 的父节点。

  • 如何判断树根:if (p[x]== x) // 它的父节点就是它本人
  • 如何求 x 的汇合编号: while (p[x]!= x)x= p[x];
  • 如何合并两个汇合:px 是 x 的汇合编号，py 是 y 的汇合编号。p[x]=y

优化办法

门路压缩（罕用），按秩合并。

门路压缩 就是将曾经找到根节点的所有点，批改其父节点为根节点，以达到升高工夫复杂度近似为 O（1）的目标。（因为若始终采纳循环来找父节点，工夫复杂度将会由树的高度决定，非常冗余）。这里是采纳递归的形式实现。

留神：通常 scanf 在读字符串时会主动疏忽空格和回车。因而在用 scanf 读入一个字符或者字母时，举荐采纳字符串的模式 %S。

例题：合并汇合

一共有 n 个数，编号是 1∼n，最开始每个数各自在一个汇合中。

当初要进行 m 个操作，操作共有两种：

  1. M a b，将编号为 a 和 b 的两个数所在的汇合合并，如果两个数曾经在同一个汇合中，则疏忽这个操作；
  2. Q a b，询问编号为 a 和 b 的两个数是否在同一个汇合中；

输出格局

第一行输出整数 n 和 m。

接下来 m 行，每行蕴含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输入格局

对于每个询问指令 Q a b，都要输入一个后果，如果 a 和 b 在同一汇合内，则输入 Yes，否则输入 No。

每个后果占一行。

数据范畴

$1≤n,m≤10^5$

输出样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输入样例：

Yes
No
Yes

code

#include <iostream>
using namespace std;

const int N = 100010;

int p[N];

int find(int x)
{
    // 留神这里是通过 递归 的形式进行查找并且门路压缩的
    // 因为返回时逐层返回，因而会把每一层的父节点都置为根节点
    if(p[x] != x) p[x] = find(p[x]);
    // 返回根节点 即 p[x] == x 的节点
    return p[x];
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)p[i] = i;
    
    while(m --)
    {char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if(*op == 'M') p[find(a)] = find(b);
        else
        {if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

例题：连通块中点的数量

给定一个蕴含 n 个点（编号为 1∼n）的无向图，初始时图中没有边。

当初要进行 m 个操作，操作共有三种：

  1. C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
  2. Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
  3. Q2 a，询问点 a 所在连通块中点的数量；

输出格局

第一行输出整数 n 和 m。

接下来 m 行，每行蕴含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输入格局

对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输入 Yes，否则输入 No。

对于每个询问指令 Q2 a，输入一个整数示意点 a 所在连通块中点的数量

每个后果占一行。

数据范畴

$1≤n,m≤10^5$

输出样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输入样例：

Yes
2
3

code

#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int p[N], cnt[N];

int find (int x)
{if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    int n, m;
    cin >> n>> m;
    for(int i = 1; i <= n; i ++)
    {p[i] = i;
        cnt[i] = 1;
    }
    
    while(m --)
    {
        string op;
        cin >> op;
        int a, b;

        if(op == "C")
        {
            cin >> a >> b;
            if(find(a) == find(b)) continue; // 如果同汇合 则跳过 防止屡次合并
            cnt[find(b)] += cnt[find(a)];
            p[find(a)] = find(b);
        }
        
        if(op == "Q1")
        {
            cin >> a >> b;
            if(find(b) == find(a)) puts("Yes");
            else puts("No");
        }
        
        if(op == "Q2")
        {
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
        
    }
    return 0;
}

以上的版本比拟便于了解（举荐），也能够采纳如下的写法·：

#include<iostream>
using namespace std;

const int N = 100010;
int n, m;
int p[N], cnt[N];

int find(int x)
{if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++)
    {p[i] = i;
        cnt[i] = 1;
    }
    
    while(m --)
    {
        string op;
        cin >> op;
        int a, b;
        
        if(op == "C")
        {
            cin >> a >> b;
            // 留神这里是先将两个根节点取出来了
            a = find(a), b = find(b);
            // 防止同一汇合中进行合并
            if(a != b)
            {
                // 而后再进行改变
                p[a] = b;
                cnt[b] += cnt[a];
                // 如果不先取出两个根节点保留，而是间接进行操作的话，必须要先进行计数赋值，再改变根节点（即下面两句话颠倒过去，否则会造成原来的根节点产生了变动，存储的 cnt 也相应扭转了）}
        }
        else if(op == "Q1")
        {
            cin >> a >> b;
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }
    return 0;
}

这里须要额定留神的是：a = find(a), b = find(b)先将两个根节点取出来了，如果不先取出两个根节点保留，而是间接进行操作的话，必须要先进行计数赋值，再改变根节点（否则会造成原来的根节点产生了变动，存储的 cnt 也相应扭转了）

图解剖析：

将 1,5 合并，find(1) = 3 find(5) = 4

p[3] = 4

这时候有 8 个点相连接，合并的数目更新形式:

  • size[3] = 4 以 3 为根节点下有 4 个连通块
  • size[4] = 4 以 4 为根节点下有 4 个连通块

更新 4 节点的连通块状况 size[4] = size[4] + size[3] = 8

模板总结

int find(int x)
{
    // 留神这里是通过递归的形式进行查找并且门路压缩的
    // 因为返回时逐层返回，因而会把每一层的父节点都置为根节点
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

例题：食物链

动物王国中有三类动物 A,B,C，这三类动物的食物链形成了乏味的环形。

A 吃 B，B 吃 C，C 吃 A。

现有 N 个动物，以 1∼N 编号。

每个动物都是 A,B,C 中的一种，然而咱们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所形成的食物链关系进行形容：

第一种说法是 1 X Y，示意 X 和 Y 是同类。

第二种说法是 2 X Y，示意 X 吃 Y。

此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真的，有的是假的。

当一句话满足下列三条之一时，这句话就是实话，否则就是真话。

  1. 以后的话与后面的某些真的话抵触，就是实话；
  2. 以后的话中 X 或 Y 比 N 大，就是实话；
  3. 以后的话示意 X 吃 X，就是实话。

你的工作是依据给定的 N 和 K 句话，输入实话的总数。

输出格局

第一行是两个整数 N 和 K，以一个空格分隔。

以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D 示意说法的品种。

若 D=1，则示意 X 和 Y 是同类。

若 D=2，则示意 X 吃 Y。

输入格局

只有一个整数，示意实话的数目。

数据范畴

$1≤N≤50000$,
$0≤K≤100000$

输出样例：

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

输入样例：

3

根本剖析

余 1：能够吃根节点

余 2：能够被根节点吃

余 0：与根节点是同类

因而合并后，x 与 y 同类，则能够说 d[x] + d[px] 与 d[y] 在 mod3 的意义下是同余的，即能够用以下式子示意

(d[x] + d[px] - d[y]) % 3 = 0 可知 d[px] = d[y] - d[x]

code

#include <iostream>

using namespace std;

const int N = 50010;

int n, m;
//p[]寻找根节点，d[]求到父节点（find 更新前）/ 根节点（find 更新后）的间隔
int p[N], d[N];

int find(int x)
{if (p[x] != x)
    {int u = p[x];  // u 记录旧的父节点
        p[x] = find(p[x]); // 门路压缩，新父节点变成根节点了
        d[x] += d[u];  // x 到新根节点的间隔等于 x 到旧父节点的间隔加上旧父节点到根节点的间隔
        
        // 以下版本不好了解：// 保留根节点
        //int t = find(p[x]);
        // 更新间隔 d[x] = d[x] + d[p[x]]
        //d[x] += d[p[x]];
        // 指向根节点
        //p[x] = t;
    }
    return p[x];
}

int main()
{scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++) p[i] = i;

    int res = 0;
    while (m --)
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        // 条件 2：以后的话中 X 或 Y 比 N 大，就是实话
        if (x > n || y > n) res ++ ;
        else
        {
            // 寻找根节点
            int px = find(x), py = find(y);
            if (t == 1)
            {
                // 若在同一个汇合 则同类相距间隔必是 3 的倍数 若不是则是实话
                // 其中 (d[x] - d[y]) % 3 不可写为 d[x] % 3 != d[y] % 3, 因为 d[x], d[y] 可能为正数（一正一负），可改做 (d[x] % 3 + 3) % 3 != (d[y] % 3 + 3) % 3, 留神：正数 mod 负数为正数
                // 相对来说间接写(d[x] - d[y]) % 3 还是比拟简洁的，因为不为 0 就是实话
                if (px == py && (d[x] - d[y]) % 3) res ++ ;
                else if (px != py)
                {
                    // 若不在同一个汇合，x 合并到 y 中
                    p[px] = py;
                    // 两个间隔相减就会变成正数，代码中有 d[px] = d[y] - d[x];
                    d[px] = d[y] - d[x];
                }
            }
            else
            {// 若在同一个汇合 则 x 吃 y 必满足 mod3 的意义下 d[x]比 d[y]大 1  可示意为(d[x] - d[y] - 1) mod 3 = 0
                if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
                else if (px != py)
                {p[px] = py;
                    // (d[x] - d[y] - 1) % 3 == 0，d[x] + d[px] - 1 = d[y]
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }

    printf("%d\n", res);
    return 0;
}

⚠对于公式的具体了解：如果还是难以了解，能够尝试模仿一下过程：

1. 初始状态下：

2. 一般状况下：

⚠其中对于 find 的具体了解：

find(x)有两个性能：1 门路压缩, 2 更新 d[x]

假如有一棵树 a -> b -> c -> d，根节点为 d。d[b]一开始等于 b、c 之间的间隔，再执行完门路压缩命令之后，d[b] 等于 b、d 之间的间隔。d[a] += d[b]: 为了确保 d[a]等于 节点 a、d 的间隔，d[b]必须等于 b、d 的间隔，所以要先调用 find(b)更新 d[b]，同时 p[x] = find(b)会扭转 p[x]的值，后果就会变成 d[a] += d[d], 所以先用一个变量把 p[a]的值存起来。

int t = p[x]; // t = p[a] = b
p[x] = find(p[x]); // b = find(b) 每次递归都会对门路进行压缩
d[x] += d[t];// d[a] = d[a](a --> b) + d[b](b --> d)
// find(b):
int t = p[x]; // t = p[b] = c
p[x] = find(p[x]); // c = find(c)
d[x] += d[t];// d[b] = d[b](b --> c) + d(c --> d)

要害就是既要先执行 find(p[x])，又要让 d[x] += d[p[x]]中 p[x]的值放弃不变，所以代码能够这么写

int t = p[x];
p[x] = find(p[x]);
d[x] += d[t];
退出移动版