算法训练营第六十九天 | 并查集理论基础、寻找存在的路径、冗余连接、冗余连接II_卡码网

​

并查集理论基础

• 并查集解决的主要是连通性问题，即判断两个节点是否连通，无论是直接连通还是间接连通

思路方法：

• 用一个数组记录每个节点的父节点，这个父节点是可以变化的，在加入新的边的过程中，我们可以不断更新这个数组使其指向一个最远的节点，遇到并不指向一处的新节点，则将这个最远的节点指向新节点；

• 如果两个节点都是新节点，则将前面一个节点的父节点设置为后一个节点

本质

• 并查集的背后，其实就是一个路径压缩的过程​​​​​​​

模板代码如下：

int father[101];

void init() {
    for (int i = 0; i <= 100; i++) father[i] = i;
}

int find(int a) {
    while (father[a] != a) {
        a = father[a];
    }
    return a;
}

bool isSame(int a, int b) {
    a = find(a);
    b = find(b);
    return a == b;
}

void join(int a, int b) {
    if (isSame(a, b)) return;
    father[find(a)] = b;
    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

卡码网107 寻找存在的路径

这是一个无向图找路径的问题，之前我们已经用深搜的方法将路径打印出来了，但这题只需要找是否存在路径，那么就可以用并查集判断连通性来节省时间了

#include <iostream>

using namespace std;

int father[101];

void init() {
    for (int i = 0; i <= 100; i++) father[i] = i;
}

int find(int a) {
    while (father[a] != a) {
        a = father[a];
    }
    return a;
}

bool isSame(int a, int b) {
    a = find(a);
    b = find(b);
    return a == b;
}

void join(int a, int b) {
    if (isSame(a, b)) return;
    father[find(a)] = b;
    return;
}

int main() {
    int m, n;
    cin >> n >> m;
    int s, t;
    init();
    for (int i = 0; i < m; i++) {
        cin >> s >> t;
        join(s, t);
    }
    int source, destination;
    cin >> source >> destination;
    if (isSame(source, destination)) cout << 1 << endl;
    else cout << 0 << 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

卡码网108 冗余路径

其实本质上是要从环中删除一条边，如果遇到两个已经连同的节点又在一条新输入的边中出现时，即可打印输出了。和题目要求中输出最后一条可删除的边的要求并不冲突

#include <iostream>

using namespace std;

int father[1001];

void init() {
    for (int i = 0; i <= 1000; i++) father[i] = i;
}

int find(int a) {
    while (father[a] != a) {
        a = father[a];
    }
    return a;
}

bool isSame(int a, int b) {
    a = find(a);
    b = find(b);
    return a == b;
}

void join(int a, int b) {
    if (isSame(a, b)) return;
    father[find(a)] = b;
    return;
}

int main() {
    int n;
    cin >> n;
    int s, t;
    init();
    for (int i = 0; i < n; i++) {
        cin >> s >> t;
        if (isSame(s, t)) {
            cout << s << ' ' << t << endl;
            return 0;
        }
        join(s, t);
    }
    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

卡码网109 冗余连接II

这题加上了对于节点入度的判断，入度为2的节点需要着重处理，如果删除后其余节点仍旧能够构成有向环，说明删除的边是必不可少的边，而留下的才是构成了有向环的那一条边
而如果没有入度为2的节点，直接按照上一题的删除思路来就行了

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

int father[1001];

void init() {
    for (int i = 0; i <= 1000; i++) father[i] = i;
}

int find(int a) {
    while (father[a] != a) {
        a = father[a];
    }
    return a;
}

bool isSame(int a, int b) {
    a = find(a);
    b = find(b);
    return a == b;
}

void join(int a, int b) {
    if (isSame(a, b)) return;
    father[find(a)] = b;
    return;
}

void getRemovedEdge(vector<vector<int>>& edge) {
    init();
    for (int i = 0; i < edge.size(); i++) {
        if (isSame(edge[i][0], edge[i][1])) {
            cout << edge[i][0] << ' ' << edge[i][1] << endl;
            return;
        } else {
            join(edge[i][0], edge[i][1]);
        }
    }
}

int isTreeAfterRemoveEdge(const vector<vector<int>>& edge, int deleteEdge) {
    init(); // 初始化并查集
    for (int i = 0; i < edge.size(); i++) {
        if (i == deleteEdge) continue;
        if (isSame(edge[i][0], edge[i][1])) { // 构成有向环了，一定不是树
            return false;
        }
        join(edge[i][0], edge[i][1]);
    }
    return true;
}


int main() {
    int n;
    cin >> n;
    int s, t;
    vector<vector<int>> edge;
    vector<int> inDegree(n+1, 0);
    for (int i = 0; i < n; i++) {
        cin >> s >> t;
        inDegree[t]++;
        edge.push_back({s, t});
    }
    vector<int> vec;
    for (int i = n-1; i >= 0; i--) {
        if (inDegree[edge[i][1]] == 2) {
            vec.push_back(i);
        }
    }
    if (vec.size() > 0) {
        if (isTreeAfterRemoveEdge(edge, vec[0])) {
            cout << edge[vec[0]][0] << ' ' << edge[vec[0]][1] << endl;
        }    
        else {
            cout << edge[vec[1]][0] << ' ' << edge[vec[1]][1] << endl;
        }
    }
    else 
        getRemovedEdge(edge);
    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
77
78
79
80
81
82
83