kuangbin 专题五 并查集

Posted on Edited on In

题目详单见 [kuangbin带你飞]专题1-23。
算法介绍见 并查集 - OI Wiki。

POJ-2236 Wireless Network

每修复一台电脑，就尝试连接其他已修复的电脑，使用并查集维护连通关系。

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
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1002;
int n, x[N], y[N], f[N];
double d;
bool st[N];
char op;
int p, q;
int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}
bool connected(int i, int j)
{
    return find(i) == find(j);
}
void connect(int i, int j)
{
    f[find(i)] = find(j);
}
double get_dist(int i, int j)
{
    return sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
}
int main()
{
    cin >> n >> d;
    for (int i = 1; i <= n; ++i)
    {
        cin >> x[i] >> y[i];
        f[i] = i;
    }
    while (cin >> op)
    {
        if (op == 'O')
        {
            cin >> p;
            st[p] = 1;
            for (int i = 1; i <= n; ++i)
                if (i != p && st[i] && get_dist(i, p) <= d)
                    connect(i, p);
        }
        else
        {
            cin >> p >> q;
            cout << (connected(p, q) ? "SUCCESS" : "FAIL") << endl;
        }
    }
    return 0;
}

POJ-1611 The Suspects

使用并查集维护关系，找出所有与 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
#include <iostream>
#include <vector>
using namespace std;
const int N = 30000;
int n, m, k, x, p[N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
void connect(int x, int y)
{
    p[find(x)] = find(y);
}
int main()
{
    while (cin >> n >> m, n)
    {
        for (int i = 0; i < n; ++i)
            p[i] = i;
        while (m--)
        {
            cin >> k >> x;
            int px = find(x);
            while (--k)
            {
                cin >> x;
                connect(x, px);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i)
            if (find(i) == find(0))
                ++ans;
        cout << ans << endl;
    }
    return 0;
}

HDU-1213 How Many Tables

使用并查集维护连通关系，统计连通块数目。

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
#include <iostream>
using namespace std;
const int N = 1001;
int t, n, m, a, b, p[N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
void connect(int x, int y)
{
    p[find(x)] = find(y);
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)
            p[i] = i;
        while (m--)
        {
            cin >> a >> b;
            connect(a, b);
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            if (find(i) == i)
                ++ans;
        cout << ans << endl;
    }
    return 0;
}

HDU-3038 How Many Answers Are Wrong

  1. 权值并查集，维护数量关系，权值表示点到根节点的区间和。
  2. 题目未提及，但是输入有多组测试用例。
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
#include <iostream>
using namespace std;
const int N = 200001;
int n, m, a, b, s, f[N], d[N], ans;
int find(int p)
{
    if (f[p] == p)
        return p;
    else
    {
        int v = find(f[p]);
        d[p] += d[f[p]];
        return f[p] = v;
    }
}
int main()
{
    while (cin >> n >> m)
    {
        ans = 0;
        for (int i = 0; i <= n; ++i)
            f[i] = i, d[i] = 0;
        while (m--)
        {
            cin >> a >> b >> s;
            --a;
            int fa = find(a), fb = find(b);
            if (fa == fb)
            {
                if (d[b] - d[a] != s)
                    ++ans;
            }
            else
            {
                f[fb] = fa;
                d[fb] = s + d[a] - d[b];
            }
        }
        cout << ans << endl;
    }
    return 0;
}

POJ-1182 食物链

POJ 比较慢，慎用 iostream。

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
#include <cstdio>
using namespace std;
const int N = 50001;
int n, k, t, x, y, p[N], d[N], ans;
int find(int x)
{
    if (p[x] != x)
    {
        int root = find(p[x]);
        d[x] = (d[x] + d[p[x]]) % 3;
        p[x] = root;
    }
    return p[x];
}
int join(int t, int x, int y)
{
    int px = find(x), py = find(y);
    if (px == py)
    {
        if ((d[x] - d[y] + 3) % 3 == t - 1)
            return 0;
        return 1;
    }
    p[px] = py;
    d[px] = (-d[x] + t - 1 + d[y] + 3) % 3;
    return 0;
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i <= n; ++i)
        p[i] = i, d[i] = 0;
    while (k--)
    {
        scanf("%d%d%d", &t, &x, &y);
        if (x > n || y > n)
            ++ans;
        else if (x == y && t == 2)
            ++ans;
        else
            ans += join(t, x, y);
    }
    printf("%d\n", ans);
    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
#include <cstdio>
using namespace std;
const int N = 50001;
int n, k, d, x, y, p[N * 3], ans;
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
void join(int x, int y)
{
    p[find(x)] = find(y);
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n * 3; ++i)
        p[i] = i;
    while (k--)
    {
        scanf("%d%d%d", &d, &x, &y);
        if (x > n || y > n)
            ++ans;
        else if (x == y && d == 2)
            ++ans;
        else if (d == 1)
        {
            if (find(x) == find(y + n) || find(x + n) == find(y))
                ++ans;
            else
                join(x, y), join(x + n, y + n), join(x + n + n, y + n + n);
        }
        else
        {
            if (find(x) == find(y) || find(x + n) == find(y))
                ++ans;
            else
                join(x, y + n), join(x + n, y + n + n), join(x + n + n, y);
        }
    }
    printf("%d\n", ans);
    return 0;
}

POJ-1417 True Liars

并查集加 01 背包。首先用并查集分组，每一组内只有两类，非此即彼。在此基础上做 01 背包，并记录选择方案，方案数刚好为 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
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
#include <cstdio>
#include <cstring>
const int N = 601;
using namespace std;
int n, p1, p2, x, y;
char a[4];
int p[N], d[N], tot, g[N], cnt[N][2];
int dp[N][N], path[N][N];
bool flag[N][2];
int find(int x)
{
    if (p[x] != x)
    {
        int px = find(p[x]);
        d[x] ^= d[p[x]];
        p[x] = px;
    }
    return p[x];
}
void join(int x, int y, int t)
{
    int px = find(x), py = find(y);
    if (px != py)
    {
        p[py] = px;
        d[py] = d[x] ^ d[y] ^ t;
    }
}
int main(void)
{
    while (scanf("%d%d%d", &n, &p1, &p2), n + p1 + p2)
    {
        for (int i = 1; i <= p1 + p2; ++i)
            p[i] = i, d[i] = 0;
        while (n--)
        {
            scanf("%d%d%s", &x, &y, a);
            join(x, y, a[0] == 'y' ? 0 : 1);
        }
        if (p1 == p2) {
            printf("no\n");
            continue;
        }
        memset(g, 0, sizeof g);
        memset(cnt, 0, sizeof cnt);
        memset(dp, 0, sizeof dp);
        memset(path, 0, sizeof path);
        memset(flag, 0, sizeof flag);
        // count and index connected components.
        tot = 0;
        for (int i = 1; i <= p1 + p2; ++i)
            if (find(i) == i)
                g[i] = ++tot;
        // count types of each group.
        for (int i = 1; i <= p1 + p2; ++i)
            cnt[g[find(i)]][d[i]]++;
        // count of solutions
        // choosing within [0...i] group to get sum(...) = j.
        dp[0][0] = 1;
        for (int i = 1; i <= tot; ++i)
            for (int j = 0; j <= p1 + p2; ++j)
            {
                if (j - cnt[i][0] >= 0 && dp[i - 1][j - cnt[i][0]])
                {
                    dp[i][j] += dp[i - 1][j - cnt[i][0]];
                    path[i][j] = cnt[i][0];
                }
                if (j - cnt[i][1] >= 0 && dp[i - 1][j - cnt[i][1]])
                {
                    dp[i][j] += dp[i - 1][j - cnt[i][1]];
                    path[i][j] = cnt[i][1];
                }
            }
        if (dp[tot][p1] != 1)
            printf("no\n");
        else
        {
            for (int i = tot, j = p1; j > 0 && i > 0; --i)
            {
                if (path[i][j] == cnt[i][0])
                    flag[i][0] = 1;
                else
                    flag[i][1] = 1;
                j -= path[i][j];
            }
            for (int i = 1; i <= p1 + p2; i++)
                if (flag[g[find(i)]][d[i]])
                    printf("%d\n", i);
            printf("end\n");
        }
    }
    return 0;
}

POJ-1456 Supermarket

贪心+并查集。优先买贵的，贵的尽量在 ddl 买，这样可以给买其他物品留些时间避免超时。按价格排序后依次处理，每一个都在 ddl 那天往前找可用的时间。这样找空闲时间的复杂度最坏为 。所以用并查集优化，每个节点代表距离当前 ddl 最近的可用空闲日期。每次用掉一天就连接当前点和前一点。

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
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
const int N = 10001;
int n, f[N];
vector<pii> a;
int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}
int main()
{
    while (~scanf("%d", &n))
    {
        a.clear();
        int maxd = 0, ans = 0;
        for (int i = 0, p, d; i < n; ++i)
        {
            scanf("%d%d", &p, &d);
            a.push_back({-p, d});
            maxd = max(maxd, d);
        }
        for (int i = 0; i <= maxd; ++i)
            f[i] = i;
        sort(a.begin(), a.end());
        for (int i = 0; i < a.size(); ++i)
        {
            int p = -a[i].first, d = a[i].second;
            int fd = find(d);
            if (fd > 0) {
                ans += p;
                f[fd] = fd - 1;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

POJ-1733 Parity game

考虑取值范围，，需要离散化数据。然后用并查集维护节点关系（奇偶，非此即彼），发现矛盾可提前退出。

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 10010;
int n, m, p[N * 2];
unordered_map<int, int> s;
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
int get(int x)
{
    if (s.find(x) == s.end())
        s[x] = ++n;
    return s[x];
}
int main()
{
    cin >> n >> m;
    n = 0;
    for (int i = 0; i < N * 2; ++i)
        p[i] = i;
    int ans = m;
    for (int i = 1; i <= m; ++i)
    {
        int a, b;
        string type;
        cin >> a >> b >> type;
        a = get(a - 1), b = get(b);
        if (type == "even")
        {
            if (find(a + N) == find(b))
            {
                ans = i - 1;
                break;
            }
            p[find(a)] = find(b);
            p[find(a + N)] = find(b + N);
        }
        else
        {
            if (find(a) == find(b))
            {
                ans = i - 1;
                break;
            }
            p[find(a + N)] = find(b);
            p[find(a)] = find(b + N);
        }
    }
    cout << ans << endl;
    return 0;
}

POJ-1984 Navigation Nightmare

1
// TODO

POJ-2492 A Bug’s Life

01 关系，非此即彼，用并查集维护。

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
#include <cstdio>
#define N 2001
using namespace std;
int t, n, m, f[N * 2];
int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}
void join(int x, int y)
{
    f[find(x)] = find(y);
}
int main()
{
    scanf("%d", &t);
    for (int _ = 1, a, b; _ <= t; ++_)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n * 2; ++i)
            f[i] = i;
        bool flag = 0;
        while (m--)
        {
            scanf("%d%d", &a, &b);
            if (find(a) == find(b) || find(a + n) == find(b + n))
                flag = 1;
            else
                join(a, b + n), join(a + n, b);
        }
        printf("Scenario #%d:\n", _);
        printf(flag ? "Suspicious bugs found!\n\n" : "No suspicious bugs found!\n\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
#include <cstdio>
#define N 2001
using namespace std;
int t, n, m, f[N], d[N];
int find(int x)
{
    if (f[x] != x)
    {
        int root = find(f[x]);
        d[x] = d[x] ^ d[f[x]];
        f[x] = root;
    }
    return f[x];
}
void join(int x, int y)
{
    int fx = find(x), fy = find(y);
    if (fx != fy)
        f[fx] = fy, d[fx] = 1 ^ d[x] ^ d[y];
}
int main()
{
    scanf("%d", &t);
    for (int _ = 1, a, b; _ <= t; ++_)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
            f[i] = i, d[i] = 0;
        bool flag = 0;
        while (m--)
        {
            scanf("%d%d", &a, &b);
            int fa = find(a), fb = find(b);
            if (fa == fb)
            {
                if (d[a] == d[b])
                    flag = 1;
            }
            else
                join(a, b);
        }
        printf("Scenario #%d:\n", _);
        printf(flag ? "Suspicious bugs found!\n\n" : "No suspicious bugs found!\n\n");
    }
    return 0;
}

POJ-2912 Rochambeau

类似上面的True Liars。不过没有 01 背包这种“巧妙”的枚举，这题是“暴力”枚举每个人当裁判的可能性。若某人不可能是裁判，记录确定其不可能性的时间点。这样一来，如果最后只有一个小孩是裁判，那取其他人的不可能时间点的最大值，就是确定小孩可以当裁判（唯一裁判）的最早时间。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 500
#define M 2001
using namespace std;
int n, m, a[M], b[M];
char c[M];
int p[N], d[N];
bool st[N]; // is `i` a judge or not.
int f[N];   // in which turn can we confirm that `i` is not a judge.
int find(int x)
{
    if (p[x] != x)
    {
        int root = find(p[x]);
        d[x] = (d[x] + d[p[x]]) % 3;
        p[x] = root;
    }
    return p[x];
}
bool check(int k) // check if the kth round is valid.
{
    int x = a[k], y = b[k];
    int t = 1;
    if (c[k] == '=')
        t = 0;
    else if (c[k] == '>')
        swap(x, y); // so that it's always 'x>y'.
    int px = find(x), py = find(y);
    if (px == py)
    {
        if (d[x] != (d[y] + t) % 3)
            return 0;
    }
    else
    {
        p[px] = py;
        d[px] = ((t + d[y] - d[x]) % 3 + 3) % 3;
    }
    return 1;
}
int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        for (int i = 1; i <= m; ++i)
            scanf("%d%c%d", &a[i], &c[i], &b[i]);
        memset(f, 0, sizeof f);
        int judge_cnt = 0, judge_idx = 0;
        for (int i = 0; i < n; ++i) // for each child.
        {
            for (int j = 0; j < n; ++j)
                p[j] = j, d[j] = 0;
            bool is_judge = 1;             // assume that `i` is a judge.
            for (int j = 1; j <= m; ++j)   // for each rounds.
                if (a[j] != i && b[j] != i // `i` (the judge) is not involved.
                    && !check(j))          // check if it's still valid.
                {
                    is_judge = 0;
                    f[i] = j; // at jth round we can confirm that `i` is not a judge.
                    break;
                }
            if (is_judge)
            {
                ++judge_cnt;
                judge_idx = i;
            }
        }
        if (!judge_cnt)
            puts("Impossible");
        else if (judge_cnt > 1)
            puts("Can not determine");
        else
            printf("Player %d can be determined to be the judge after %d lines\n", judge_idx, *max_element(f, f + n));
    }
    return 0;
}

ZOJ-3261 Connections in Galaxy War

并查集删除边，需要反着做。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#define N 10000
#define Q 50000
using namespace std;
int n, p[N], m, q, qs[Q][3];
char s[8];
set<int> g; // tunnels.
int fa[N], maxp[N], maxp_idx[N];
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void unite(int x, int y)
{
    x = find(x), y = find(y);
    if (x != y)
    {
        fa[y] = x;
        if (maxp[x] == maxp[y])
            maxp_idx[x] = min(maxp_idx[x], maxp_idx[y]);
        else if (maxp[x] < maxp[y])
            maxp[x] = maxp[y], maxp_idx[x] = maxp_idx[y];
    }
}
int ab_to_idx(int a, int b)
{
    if (a > b)
        swap(a, b);       // always take the smaller one as a.
    return (a << 14) + b; // then map to 32-bit integer.
}
pair<int, int> idx_to_ab(int idx)
{
    int b = ((1 << 14) - 1) & idx;
    int a = (idx - b) >> 14;
    return {a, b};
}
int main()
{
    bool flag = 0;
    while (~scanf("%d", &n))
    {
        if (flag)
            puts("");
        else
            flag = 1;
        g.clear();
        for (int i = 0; i < n; ++i)
            scanf("%d", &p[i]);
        scanf("%d", &m);
        for (int i = 0, a, b; i < m; ++i)
        {
            scanf("%d%d", &a, &b);
            g.insert(ab_to_idx(a, b));
        }
        scanf("%d", &q);
        vector<pair<int, int>> ds;
        for (int i = 0, a, b; i < q; ++i)
        {
            scanf("%s%d", s, &a);
            if (s[0] == 'd')
            {
                scanf("%d", &b);
                qs[i][0] = 0, qs[i][1] = a, qs[i][2] = b;
                g.erase(ab_to_idx(a, b)); // destory first.
            }
            else
                qs[i][0] = 1, qs[i][1] = a;
        }
        for (int i = 0; i < n; ++i)
            fa[i] = i, maxp[i] = p[i], maxp_idx[i] = i;
        for (int idx : g)
        {
            auto [a, b] = idx_to_ab(idx);
            unite(a, b); // build graph.
        }
        vector<int> ans;
        for (int i = q - 1; i >= 0; --i)
        {
            if (qs[i][0] == 0) // reverse destroyed tunnel.
                unite(qs[i][1], qs[i][2]);
            else // query.
            {
                int a = qs[i][1], f = find(a);
                ans.push_back(maxp[f] <= p[a] ? -1 : maxp_idx[f]);
            }
        }
        for (int i = ans.size() - 1; i >= 0; --i)
            printf("%d\n", ans[i]);
    }
    return 0;
}

HDU-1272 小希的迷宫

POJ-1308 Is It A Tree?