BZOJ3060《Tour de Byteotia》

二月 04, 2019 1981

并查集板子题（雾

题面

权限题，题面请自行寻找
用小刀刮开涂层来获取题目地址
访问 DarkBZOJ 来获取题面

解析

用并查集维护一下连通性

下文我们称「编号小于等于k的点」为「奇特点」

显然和奇特点没有关系的边删不删都无所谓，不影响答案，所以我们可以放心地把这些边加入并查集。

然后我们枚举所有的与奇特点相连的边，尝试将这条边加入并查集。
如果这条边的两个点不连通，就可以放心地将这条边加入并查集，否则++ans

最后输出ans即可

代码实现

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
#include <algorithm>
#include <iostream>
#include <cstring>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 1000000 + 10;
const int MAXM = 2000000 + 10;

struct UnionFind {
    int seq[MAXN];
    
    UnionFind() {
        memset(seq, 0, sizeof seq);
    }
    
    int Find(int x) {
        if (seq[x] == 0) return x;
        return seq[x] = Find(seq[x]);
    }
    
    bool Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        if (x == y) return false;
        seq[x] = y;
        return true;
    }
} U;

struct Edge {
    int f, t;
    // from to
    
    Edge() { f = t = 0; }
} edge[MAXM << 1];

int n, m, k, cnt;

inline void addEdge(int u, int v) {
    edge[++cnt].f = u;
    edge[cnt].t = v;
}

int main() {
    IMPROVE_IO();
    cin >> n >> m >> k;
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
        int prev = 0, next = 0;
        cin >> prev >> next;
        addEdge(prev, next);
    }
    for (int e = 1; e <= m; ++e) {
        if (!(edge[e].f <= k || edge[e].t <= k)) {
            U.Union(edge[e].f, edge[e].t);
        }
    }
    for (int e = 1; e <= m; ++e) {
        if (edge[e].f <= k || edge[e].t <= k) {
            if (!U.Union(edge[e].f, edge[e].t)) ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}