acwing算法基础课笔记-并查集

发表于 更新于 分类于 Artalk： loading...

前言

并查集的基本原理参见关于并查集

参考知乎专栏-算法笔记：并查集

基本代码

1
2
3
4
5
6
7
8
9
10
// find 函数：返回x的根（祖宗）节点
int find(int x) {
    // 路径压缩
    if (p[x] != x) p[x] = find(p[x]); // 若p[x]==x，则x为树根节点 
    return p[x];
}

// 将节点a和节点b 所在的集和 合并
p[find(a)] = find(b);

简单提一下，按秩合并。这里的秩rank()rank()，具体指的是并查集合的深度。在合并时，将秩较小的集合，合并到秩较大的集合上，效率较高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 按秩合并
void merge(int a, int b) {
    int a = find(a), b = find(b); // 先保存下来a和b的根节点
    if (cnt[a] <= cnt[b]) {
        p[a] = b; // 将秩小的根挂到秩较大的根节点上面
    }
    else {
        p[b] = a;
    }
    // 考虑两个集合秩相同的情况下，合并会导致深度加一
    if (cnt[a] == cnt[b] && a != b) {
        cnt[b] ++;
    }
}

java类实现并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class DSU {
    int[] p, rank;
    public DSU(int n) {
        this.p = new int[n];
        this.rank = new int[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
            rank[i] = 1;
        }
    }
    int find(int u) {
        if (p[u] != u) p[u] = find(p[u]);
        return p[u];
    }
    void union(int x, int y) {
        int xx = find(x), yy = find(y);
        if (rank[xx] <= rank[yy]) p[xx] = yy;
        else p[yy] = xx;
        if (rank[xx] == rank[yy] && xx != yy) rank[yy]++;
    }
}

以下举例的图片来自算法笔记：并查集

preview

考虑以上极端例子，左边的集合秩为4，右边集合的秩只有1

img

毫无疑问，后者的效率较高，避免的大量节点的更新。

例题

连通块中点的数量

问题链接👉🏻acwing 837. 连通块中点的数量

问题描述

给定一个包含nn个点（编号为 1∼n−11 \sim n-1）的无向图，初始时图中没有边。

现在要进行mm个操作，操作共有三种：

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

输入格式

第一行输入整数nn和mm。

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

输出格式

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

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

每个结果占一行。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>

using namespace std;
const int N = 1e5+10;

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; // 计数，也可以说是秩rank()
    }
    while (m --) {
        string op;
        int a, b;
        cin >> op;
        if (op == "C") {
            cin >> a >> b;
            if (find(a) != find(b)) {
                cnt[find(b)] += cnt[find(a)];
                p[find(a)] = find(b);
            }
        }
        else if (op == "Q1") {
            cin >> a >> b;
            if (find(a) != find(b)) puts("No");
            else puts("Yes");
        }
        else {
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }
    
    return 0;
}

加入计数功能，唯一需要注意的点是：在合并集和时，计数操作一定要在合并之前。

1
2
3
4
5
6
7
8
if (find(a) != find(b)) {
    cnt[find(b)] += cnt[find(a)];
    p[find(a)] = find(b);
    /* 错误示范
    p[find(a)] = find(b);
    cnt[find(b)] += cnt[find(a)];  
    */
}

否则就相当于，让bb所在集合元素数量翻倍，显然不合理；

acwing 240. 食物链

问题描述

image-20211217160908200

解题思路

例子

1
2
3
4
5
6
7
8
100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

image-20211217162237698

不管是什么样的信息组合，两句话确定一个关系。

并查集中维护的是节点之间的关系，如下：

对于每个节点，维持一个到根节点的距离，模三，余1表示可以吃根节点；余2表示可以被根节点吃；余0表示和根节点是同类。

路径压缩的时候，更新为每个点到根节点的距离。

代码

1
2
3
4
5
6
7
8
9
10
// 距离数组初始化为{0}

int find(int x) {
    if (p[x] != x) { // 如果x不是根节点
        int t = find(p[x]);
        d[x] += d[p[x]];
        p[x] = t;
    }
    return p[x];
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>

using namespace std;

const int N = 50010;

int n, m;
int p[N], d[N];

int find(int x)
{
    if (p[x] != x)
    {
        int t = find(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);

        if (x > n || y > n) res ++ ;
        else
        {
            int px = find(x), py = find(y);
            if (t == 1)
            {
                if (px == py && (d[x] - d[y]) % 3) res ++ ; // 考虑负数的写法
                else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[y] - d[x];
                }
            }
            else
            {
                if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
                else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }

    printf("%d\n", res);

    return 0;
}

📔博文图谱

提及本博文的链接