抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

并查集 — 2

秃头王
基础数据结构

发布于：2022年1月23日
次浏览

[TOC]

并查集(Union Find)

并查集主要讲的就是连通性问题

比如说现在咱们这个教学楼，被大水淹了比如说一楼和其它楼层都被大水淹了，就唯独咱们教室没有，可以说明什么，咱们现在就是与世隔绝了，之后呢就被大水淹没的个个楼层水是不是都可以来回走，比如流到了咱们教室恰巧关上了们，之后水就没流进来，说明什么咱们现在是与这个教学楼的一间教室都不连图，如果说咱们与隔壁是连通的，而且咱们隔壁还被大水淹没了，你说咱们这屋是不是也被淹没了。

若某个家族人员过于庞大，要判断两个是否是亲戚，确实不容易，给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

树形结构

在春秋战国时期有各种思想学术流派的成就，有 孔子 墨子 老子 还有谁比如 韩非子等等

树形结构

从我们当前图中我门可以看出我们有几个连同块 有3个对把

比如说有一天 2 号 跟 4号 打起来来了说你写的东西不如我，（这里有个规定就是说徒弟一定不如师傅）完了4号本身就是1号的徒弟肯定不如2号 当然 4号有师傅 之后4号找到自己的师傅 1 号 说今天我被人羞辱了对吧那当师傅的肯定不能做事不管对吧 之后一看 说这2号也老孔的徒弟一看这不是就是一个师傅么那就别报仇了 让 4 号 给 2 号认个错

就是下次的时候我们可以怎么看 就是先知道自己的师傅的师傅是谁对吧 在看你要找的人的师傅的师傅（这师傅可能还有师傅所有要找到最后一个师傅）是谁 如果他们最后的师傅都是同一个人那他们是不是就是一家人属于同一个师傅 （可以说明他们在通一课树中说明它们俩个连同）

其实我们在连同性中不在乎连接成什么样子谁是谁的徒弟我只在乎他们能不能连同最后的祖师，祖师爷是不是同一个人 这个两个点能不能连同

Ps 比如 （1， 2） 为一个集合

数组表示

（1，4）

（4，7）

这里代表两个集合链接，这里链接的时候你说是 1 当作根节点还是 4 当作根节点 1 其实是无所谓的。这里假定 4为根节点我们可以得到 图

集合

这两个点的连同不仅仅是两个点的连同而是两个集合的连通（其实他们都属一个个体）

比如你的爸和你妈是两个姓对吧 他们在没结婚之前是什么，两个家的人就可以比作什么两个集合，之后他们结婚了 是只有他俩是一家人么 不是吧 是两家人，这就好比我们两个点的链接。

我们可以用数组表示

初始化把每个点所在的集合初始化为其自身。

初始化加粗 为下标 我们可以用用它自身去初始化（也可以用 -1 但是后期在优化的时候会有点麻烦）

0 1 2 3
0 1 2 3
4 5 6 7
4 5 6 7
0 1 2 3
0 4 2 3
4 5 6 7
4 5 6 4

竞赛阶段我们会用到的算法 find union

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 朴素
int find_root(int x, int parent[]) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}

// 查找--优化
int find_root(int x, int parent[]) {
    if (parent[x] != x) {
        parent[x] = find_root(parent[x], parent);
    }
    return parent[x];
    // return x == parent[x] ? x : parent[x] = find_root(parent[x], parent);
    // return parent[x] = (x == parent[x] ? x : find_root(parent[x], parent));

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 合并
void merge(int x, int y, int parent[], int height[]) {
    int x_root = find_root(x, parent);
    int y_root = find_root(y, parent);
    if (x_root != y_root) {
        // parent[x_root] = y_root; // 原先代码
        // 安秩合并
        if (height[x_root] == height[y_root]) {
            parent[x_root] = y_root;
            // 相等让y的树高 +1
            height[y_root]++;
        } else if (height[x_root] > height[y_root]) {
            parent[y_root] = x_root;
        } else {
            parent[x_root] = y_root;
        }
        return ;
    }
    mark = 1;
    return ;
}

路径压缩–按秩合并

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
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
using namespace std;

const int MAX_N = 1e4;

int mark = 0;

// 初始化
void inital(int n, int parent[], int height[]) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        height[i] = 0;
    }
    return ;
}
// 路径压缩
int find_root(int x, int parent[]) {
    if (parent[x] != x) {
        parent[x] = find_root(parent[x], parent);
    }
    return parent[x];
    // 
}

// 路径压缩--非递归版
int find_root1(int x, int parent[]) {
    int k = x;
    while (parent[k] != k) {
        k = parent[k];
    }
    while (x != k) {
        int temp = parent[x];
        parent[x] = k;
        x = temp;
    }
    return k;
}

void merge(int x, int y, int parent[], int height[]) {
    int x_root = find_root(x, parent);
    int y_root = find_root(y, parent);
    if (x_root != y_root) {
        // parent[x_root] = y_root; // 原先代码
        // 按秩合并
        if (height[x_root] == height[y_root]) {
            parent[x_root] = y_root;
            // 相等让y的树高 +1
            height[y_root]++;
        } else if (height[x_root] > height[y_root]) {
            parent[y_root] = x_root;
        } else {
            parent[x_root] = y_root;
        }
        return ;
    }
    mark = 1;
    return ;
}

int main() {
    int n, m, parent[MAX_N + 10], height[MAX_N + 10];
    cin >> n >> m;
    inital(m, parent, height);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        merge(x, y, parent, height);
    }
    if (mark) cout << "有环！" << endl;
    else cout << "无环！" << endl;
    return 0;
}

路径压缩是怎么实现的

路径压缩

路径压缩_优化

检测是否存在环

我们如何去检测一个图是否存在环环路 如下

我们有 0️⃣ 1️⃣ 2️⃣ 3️⃣ 4️⃣ 5️⃣ 把每个点看成单个集合比如我们相连（0 ，1） （1，2） （1，3）（2，4）（2，3）

我们在合并时候需要先查询一下他们是否属于同一集合，如果不属于同一集合我才能合并，反之要是它们在合并就会构成回路。

如果不考虑链接红色两点，合并集合之后是{0，1，2，3，4} 我们可以得到站在任意点到达另一任意点。不构成环

如果说我们在已连接中任意选择两个去链接他一定会成环对吧。🔶

比如红色两点链接，我们可以看到 1， 2， 3 点形成了环。 形成环路

我们怎么知道他是成环了呢我们把 1 当做根结点 ，0， 2，4，3 都属于 1 的孩子或者是孙子 当你去链接 （2， 3）时候你会发现他们都属于 1 下就如我们刚才所说 🔶因为我们知道两个集合在合并的时候一定会先去找根节点。

环

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
#include<iostream>
using namespace std;

const int MAX_N = 1e4;

int mark = 0;
int parent[MAX_N + 10];

// 初始化
void inital(int n, int parent[]) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    return ;
}

int find_root(int x, int parent[]) {
    if (parent[x] != x) {
        parent[x] = find_root(parent[x], parent);
    }
    return parent[x];
}

void merge(int x, int y, int parent[]) {
    int x_root = find_root(x, parent);
    int y_root = find_root(y, parent);
    if (x_root != y_root) {
        parent[x_root] = y_root;
        return ;
    }
    mark = 1;
    return ;
}

int main() {
    int n, m;
    // 组数 最大值
    cin >> n >> m;
    inital(m, parent);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        merge(x, y, parent);
    }
    if (mark) cout << "有环！" << endl;
    else cout << "无环！" << endl;
    return 0;
}

并查集–数据结构实现

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
#include <stdlib.h>
#include <stdio.h>

struct UnionSet {
    int *parent;
};

// 初始化
UnionSet *init(int n) {
    UnionSet *U = (UnionSet *)malloc(sizeof(UnionSet));
    U->parent = (int *)malloc(sizeof(int) * (n + 1));
    for (int i = 1; i <= n; i++) {
        U->parent[i] = i;
    }
    return U;
}

int find_root(UnionSet *U, int x) {
    if (U->parent[x] != x) {
        return find_root(U, U->parent[x]);
    }
    return x;
}

void merge(UnionSet *U, int x, int y) {
    int x_root = find_root(U, x);
    int y_root = find_root(U, y);
    if (x_root != y_root) {
        U->parent[x_root] = y_root;
    }
    return ;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    UnionSet *U = init(n);
    // 进行 M 次操作
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        switch(a) {
            case 1: merge(U, b, c); break; // 合并操作
            case 2: printf("%s\n", find_root(U, b) == find_root(U, c) ? "Yes" : "No");
        }
    }
    return 0;
}

例题–题解

海贼 #71 朋友圈

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
62
63
64
65
/*************************************************************************
	> File Name: 海贼_#71并查集_路径压缩优化.cpp
	> Author: 
	> Mail: 
	> Created Time: 2021年01月18日 星期一 15时33分00秒
 ************************************************************************/

#include <iostream>
#include <cstdio>
using namespace std;

const int MAX_N = 1e4;

// 初始化
void initialization(int n, int parent[]) {
    for (int i = 1;  i <= n; i++) {
        parent[i] = i;
    }
    return ;
}

// 路径压缩
int find_root(int x, int parent[]) {
    if (parent[x] != x) {
        parent[x] = find_root(parent[x], parent);
    }
    return parent[x];
}

// 朴素算法
int find_root1(int x, int parent[]) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}

void merge(int x, int y, int parent[]) {
    int x_root = find_root(x, parent);
    int y_root = find_root(y, parent);
    if (x_root != y_root) {
        parent[x_root] = y_root;
    }
    return ;
}

int main() {
    int n, m, parent[MAX_N + 10];
    cin >> n >> m;
    initialization(n, parent);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a == 1) {
            // 添加
            merge(b, c, parent);
        } else {
            // 查看
            if (find_root(b, parent) - find_root(c, parent)) {
                printf("No\n");
            } else printf("Yes\n");
        }
    }
    return 0;
}
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
/*************************************************************************
	> File Name: 海贼_#71并查集_路径压缩_安秩合并_优化.cpp
	> Author: 
	> Mail: 
	> Created Time: 2021年01月18日 星期一 21时33分00秒
 ************************************************************************/

#include <iostream>
#include <cstdio>
using namespace std;

const int MAX_N = 1e4;

// 初始化 
void initialization(int n, int parent[], int height[]) {
    for (int i = 1;  i <= n; i++) {
        parent[i] = i;
        // 开始树高为 0
        height[i] = 0;
    }
    return ;
}

// 路径压缩
int find_root(int x, int parent[]) {
    if (parent[x] != x) {
        parent[x] = find_root(parent[x], parent);
    }
    return parent[x];
}

// 朴素算法
int find_root1(int x, int parent[]) {
    while (parent[x] != x) {
        x = parent[x];
    }
    return x;
}

void merge(int x, int y, int parent[], int height[]) {
    int x_root = find_root(x, parent);
    int y_root = find_root(y, parent);
    if (x_root != y_root) {
        if (height[x_root] == height[y_root]) {
            parent[x_root] = y_root;
            // 相等让y的树高 +1
            height[y_root]++;
        } else if (height[x_root] > height[y_root]) {
            parent[y_root] = x_root;
        } else {
            parent[x_root] = y_root;
        }
    }
    return ;
}

int main() {
    int n, m, parent[MAX_N + 10], height[MAX_N + 10];
    cin >> n >> m;
    initialization(n, parent, height);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if (a == 1) {
            // 添加
            merge(b, c, parent, height);
        } else {
            // 查看
            if (find_root(b, parent) - find_root(c, parent)) {
                printf("No\n");
            } else printf("Yes\n");
        }
    }
    return 0;
}

洛谷 P1551 亲戚

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
#include<iostream>
using namespace std;

const int MAX_N = 1e4;
int arr[MAX_N];

void initial(int n) {
    for (int i = 1; i <= n; i++) {
        arr[i] = i;
    }
}

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

void merge(int x, int y) {
    int x_root = find(x);
    int y_root = find(y);
    if (x_root != y_root) {
        arr[x_root] = y_root;
    }
    return ;
}

int main() {
    int n, m, p;
    cin >> n >> m >> p;
    initial(n);
    while (m--) {
        int mi, mj;
        cin >> mi >> mj;
        merge(mi, mj);
    }
    while (p--) {
        int mi, mj;
        cin >> mi >> mj;
        if (find(mi) == find(mj)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://tutouwang.vercel.app/2022/01/23/%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E5%B9%B6%E6%9F%A5%E9%9B%86_2/

更新于：2022年5月22日

评论