并查集模板与应用

发表于 | 更新于: | 分类于 | 本文总阅读量 次
字数统计: 1.6k | 阅读时长 ≈ 8

Union-Find算法详解 - labuladong 的算法小抄 (gitbook.io)

并查集（模板）

UF 类

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
class UF {
public:
    //构造并查集
    UF(int n) {
        count = n;
        parent = vector<int>(n, 0);
        size = vector<int>(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    //返回节点x的根节点
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];//路径压缩
            x = parent[x];
        }
        return x;
    }

    //判断p 和 q是否互相连通
    bool connected(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        return rootp == rootq;
    }

    //将p和q连通
    void Union(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        if (rootp == rootq)
            return;
        //按秩合并，高树顶点做根
        if (size[rootp] > size[rootq]) {
            parent[rootq] = rootp;
            size[rootp] += size[rootq];
        }
        else {
            parent[rootp] = rootq;
            size[rootq] += size[rootp];
        }
        count--;
    }

private:
    int count;
    vector<int> parent;
    vector<int> size; //用来存储树的大小，为按秩合并做准备
};

使用说明

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
#include <vector>
#include <iostream>

using namespace std;

class UF {
public:
    //构造并查集
    UF(int n) {
        count = n;
        parent = vector<int>(n, 0);
        size = vector<int>(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    //返回节点x的根节点
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];//路径压缩
            x = parent[x];
        }
        return x;
    }

    //判断p 和 q是否互相连通
    bool connected(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        return rootp == rootq;
    }

    //将p和q连通
    void Union(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        if (rootp == rootq)
            return;
        //按秩合并，高树顶点做根
        if (size[rootp] > size[rootq]) {
            parent[rootq] = rootp;
            size[rootp] += size[rootq];
        }
        else {
            parent[rootp] = rootq;
            size[rootq] += size[rootp];
        }
        count--;
    }

private:
    int count;
    vector<int> parent;
    vector<int> size; //用来存储树的大小，为按秩合并做准备
};

int main()
{
    int n;
    cin >> n;
    UF uf(n);  // 这里的n根据具体案例决定，比如有1，9的节点需要连通，那这里n就得是10，因为类中生成的数组是[0,9]的10个数
    // 如果使a,b连同
    int a, b;
    cin >> a >> b;
    uf.Union(a,b);
    // 如果想判断 a,b 是否连通
    uf.connected(a, b);
}

P3367 【模板】并查集

https://www.luogu.com.cn/problem/P3367

image-20210816094310822

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
#include <iostream>
#include <vector>

using namespace std;

class UF {
public:
    //构造并查集
    UF(int n) {
        count = n;
        parent = vector<int>(n, 0);
        size = vector<int>(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    //返回节点x的根节点
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];//路径压缩
            x = parent[x];
        }
        return x;
    }

    //判断p 和 q是否互相连通
    bool connected(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        return rootp == rootq;
    }

    //将p和q连通
    void Union(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        if (rootp == rootq)
            return;
        //按秩合并，高树顶点做根
        if (size[rootp] > size[rootq]) {
            parent[rootq] = rootp;
            size[rootp] += size[rootq];
        }
        else {
            parent[rootp] = rootq;
            size[rootq] += size[rootp];
        }
        count--;
    }

private:
    int count;
    vector<int> parent;
    vector<int> size; //用来存储树的大小，为按秩合并做准备
};

int main()
{
    int N, M;
    cin >> N >> M;
    UF uf(N+1);
    for (int i = 0; i < M; ++i) {
        int Z, X, Y;
        cin >> Z >> X >> Y;
        if (Z == 1) {
            uf.Union(X, Y);
        }
        else if (Z == 2) {
            if (uf.connected(X, Y)) {
                cout << "Y" << endl;
            }
            else {
                cout << "N" << endl;
            }
        }
    }
	return 0;
}

P1551 亲戚

https://www.luogu.com.cn/problem/P1551

image-20210818163607068

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
#include <iostream>
#include <vector>

using namespace std;

class UF {
public:
    //构造并查集
    UF(int n) {
        count = n;
        parent = vector<int>(n, 0);
        size = vector<int>(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    //返回节点x的根节点
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];//路径压缩
            x = parent[x];
        }
        return x;
    }

    //判断p 和 q是否互相连通
    bool connected(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        return rootp == rootq;
    }

    //将p和q连通
    void Union(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        if (rootp == rootq)
            return;
        //按秩合并，高树顶点做根
        if (size[rootp] > size[rootq]) {
            parent[rootq] = rootp;
            size[rootp] += size[rootq];
        }
        else {
            parent[rootp] = rootq;
            size[rootq] += size[rootp];
        }
        count--;
    }

private:
    int count;
    vector<int> parent;
    vector<int> size; //用来存储树的大小，为按秩合并做准备
};

int main()
{
    int n, m, p;
    cin >> n >> m >> p;

    UF uf(n+1);
    for (int i = 0; i < m; ++i) {
        int Mi, Mj;
        cin >> Mi >> Mj;
        uf.Union(Mi, Mj);
    }
    for (int j = 0; j < p; ++j) {
        int Pi, Pj;
        cin >> Pi >> Pj;
        if (uf.connected(Pi, Pj)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
	return 0;
}

P1111 修复公路

image-20210818214206051

  • TODO
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class UF {
public:
    //构造并查集
    UF(int n) {
        count = n;
        parent = vector<int>(n, 0);
        size = vector<int>(n, 1);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    //返回节点x的根节点
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];//路径压缩
            x = parent[x];
        }
        return x;
    }

    //判断p 和 q是否互相连通
    bool connected(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        return rootp == rootq;
    }

    //将p和q连通
    void Union(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        if (rootp == rootq)
            return;
        //按秩合并，高树顶点做根
        if (size[rootp] > size[rootq]) {
            parent[rootq] = rootp;
            size[rootp] += size[rootq];
        }
        else {
            parent[rootp] = rootq;
            size[rootq] += size[rootp];
        }
        count--;
    }

    // 判断所有节点是否连通
    bool allConnected() {
        int root = find(parent[1]);
        for (int i = 2; i < count; ++i) {
            int tmp = find(parent[i]);
            if (tmp != root) return false;
        }
        return true;
    }

private:
    int count;
    vector<int> parent;
    vector<int> size; //用来存储树的大小，为按秩合并做准备
};

// 按t排序
bool cmp(pair<pair<int, int>, int>& a, pair<pair<int, int>, int>& b) {
    return a.second < b.second;
}

int main()
{
    int N, M;
    cin >> N >> M;
    UF uf(N + 1);
    vector<pair<pair<int, int>, int>> record; // 记录输入((x,y), t)
    for (int i = 0; i < M; ++i) {
        int x, y, t;
        cin >> x >> y >> t;
        record.push_back(make_pair(make_pair(x, y), t));
    }
    sort(record.begin(), record.end(), cmp);

    int ans = -1;
    for (pair<pair<int, int>, int>& i : record) {
        uf.Union(i.first.first, i.first.second);
        if (uf.allConnected()) {
            ans = i.second;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

P3402 可持久化并查集

https://www.luogu.com.cn/problem/P3402



----------- 本文结束 -----------




0%