[蓝桥杯 2017 国 C] 合根植物

题意

一个 $m \times n$ 的种植园里，一开始每个格子各有一株植物。

现在给出若干对编号，表示这两个格子里的植物发生了连根，合成了同一株植物。

问最后整个种植园里一共有多少株合根植物。

题目输入里的格子已经直接编号成了 $1\dots m\times n$ ，所以不需要自己再做二维坐标转换。

思路

先看一个小数据暴力：

cpp

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

int row_cnt, col_cnt;
int k;
vector<int> g[MAXN];
bool vis[MAXN];

void dfs(int u) {
    vis[u] = true;
    for (int v : g[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> row_cnt >> col_cnt;
    int tot = row_cnt * col_cnt;

    for (int i = 1; i <= tot; i++) {
        g[i].clear();
        vis[i] = false;
    }

    cin >> k;
    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    int blocks = 0;
    for (int i = 1; i <= tot; i++) {
        if (!vis[i]) {
            blocks++;
            dfs(i);
        }
    }

    cout << blocks << '\n';
    return 0;
}

暴力把每一对连根关系都当成一条无向边，然后直接 DFS 数连通块个数。

正式做法更直接：这就是并查集模板。

把每个格子看成一个点：

一开始 $m\times n$ 个格子各自独立
读到一对连根关系 $(x, y)$ ，就把 $x$ 和 $y$ 合并到同一个集合里
如果这次合并原本不在同一个集合，就说明植物总数减少了 1

所以只要维护：

初始答案 blocks = m*n
每次成功合并，blocks--

最后输出 blocks 即可。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;

int row_cnt, col_cnt;
int k;
int fa[MAXN], sz[MAXN];

void init_dsu(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        sz[i] = 1;
    }
}

int find_root(int x) {
    if (fa[x] == x) {
        return x;
    }
    fa[x] = find_root(fa[x]);
    return fa[x];
}

bool unite(int x, int y) {
    x = find_root(x);
    y = find_root(y);
    if (x == y) {
        return false;
    }
    if (sz[x] < sz[y]) {
        swap(x, y);
    }
    fa[y] = x;
    sz[x] += sz[y];
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> row_cnt >> col_cnt;
    int tot = row_cnt * col_cnt;
    init_dsu(tot);

    cin >> k;

    int blocks = tot;
    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y;
        if (unite(x, y)) {
            blocks--;
        }
    }

    cout << blocks << '\n';
    return 0;
}

复杂度

设格子总数为 $N = m\times n$ ，连根关系数为 $k$ 。

初始化并查集 $O(N)$
每次合并均摊 $O(\alpha(N))$

总时间复杂度 $O(N + k\alpha(N))$ ，空间复杂度 $O(N)$ 。

总结

这题本质上就是在一张无向图上不断合并点，最后求连通块数量。因为输入已经给了线性编号，所以它甚至比一般的网格并查集还简单，就是一个很纯的并查集入门题。

[蓝桥杯 2017 国 C] 合根植物

目录

题意

思路

代码

复杂度

总结