🌱 P8654 [蓝桥杯 2017 国 C]合根植物 - 连通世界大冒险 题解

题目链接

洛谷原题链接

题目描述

在一个 $m$ 行 $n$ 列的网格中种植了 $m\times n$ 株植物。植物会与相邻植物"连根"（形成连通块），连通的植物群称为"合根植物"。现给出 $k$ 对连根关系，求最终合根植物的数量。

输入格式

• 第一行：$m$ 和 $n$（网格行数和列数）
• 第二行：$k$（连根关系数量）
• 接下来 $k$ 行：每行两个整数 $a$ 和 $b$，表示植物 $a$ 和 $b$ 连根

输出格式

一个整数，表示合根植物的数量

算法思路

核心思想

使用并查集管理植物的连通关系：

1. 初始化：每株植物都是独立连通块
2. 合并操作：对每对连根植物进行合并
3. 计数优化：每次成功合并，连通块数减1
4. 最终结果：剩余连通块数即为合根植物数

关键步骤

1. 问题转化：将二维网格映射为一维编号（植物编号从1到$m\times n$）
2. 并查集操作：
   • find：带路径压缩的根节点查找
   • unite：合并两个连通块（合并成功时计数减1）
3. 连通块计数：初始计数为$m\times n$，每次有效合并减1

复杂度分析

• 时间复杂度：$O(k\alpha (mn))$
  • $\alpha$ 为反阿克曼函数（接近$O(1)$)
  • $k$ 为连根关系数
• 空间复杂度：$O(mn)$

代码实现

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

// 并查集类
class UnionFind {
private:
    vector<int> parent; // 父节点数组
    int count;          // 连通块计数器
    
public:
    // 初始化并查集
    UnionFind(int n) {
        parent.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i; // 每个节点初始独立
        }
        count = n; // 初始连通块数 = 总节点数
    }
    
    // 查找根节点（带路径压缩）
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    
    // 合并节点
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return; // 已在同一连通块
        
        parent[rootY] = rootX; // 合并
        count--;               // 连通块减少
    }
    
    // 获取连通块数量
    int getCount() const {
        return count;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int m, n;
    cin >> m >> n;
    int total = m * n; // 总植物数
    
    UnionFind uf(total); // 初始化并查集
    
    int k;
    cin >> k;
    
    // 处理连根关系
    while (k--) {
        int a, b;
        cin >> a >> b;
        uf.unite(a, b); // 合并连通块
    }
    
    // 输出合根植物数量
    cout << uf.getCount() << endl;
    
    return 0;
}

代码解释

数据结构

• UnionFind类：封装并查集操作
  • parent：存储节点的父节点
  • count：动态维护连通块数量
• 核心方法：
  • find(x)：查找根节点（路径压缩优化）
  • unite(x,y)：合并两个节点（合并成功时计数减1）
  • getCount()：获取当前连通块数量

关键逻辑

1. 初始化：

   UnionFind uf(total); // 创建大小为total的并查集
   

2. 合并操作：

   uf.unite(a, b); // 合并植物a和b
   

   • 内部自动判断是否已连通
   • 只有未连通时才合并并减少计数

3. 结果输出：

   uf.getCount(); // 最终连通块数
   

算法正确性证明

计数原理

设初始连通块数 $C_0=mn$
对于每个有效合并操作：

• 当两个独立连通块合并时，$C_i=C_{i-1}-1$
• 当两个已连通块合并时，$C_i=C_{i-1}$

最终连通块数 $C_{final}$ 即为合根植物数

并查集优化

1. 路径压缩：

   parent[x] = find(parent[x]); // 压缩路径
   

   使树保持扁平，查询效率 $O(\alpha (n))$

2. 动态计数：

   if (rootX != rootY) count--;
   

   在合并时即时更新连通块数

测试样例

输入 #1

5 4
16
2 3
1 5
5 9
4 8
7 8
9 10
10 11
11 12
10 14
12 16
14 18
17 18
15 19
19 20
9 13
13 17

输出 #1

5

解释：20株植物经过16次合并后形成5个连通块：

1. {1,5,9,10,11,12,13,14,16,17,18}（11株）
2. {2,3}（2株）
3. {4,7,8}（3株）
4. {15,19,20}（3株）
5. {6}（1株）

输入 #2

3 3
5
1 2
2 3
4 5
5 6
7 8

输出 #2

3

解释：9株植物形成3个连通块：

1. {1,2,3}
2. {4,5,6}
3. {7,8,9}

复杂度证明

时间复杂度

设 $N=m\times n$（总植物数）：

• 并查集初始化：$O(N)$
• $k$ 次合并操作：每次 $O(\alpha (N))$
• 总时间：$O(N+k\alpha (N))\approx O(k)$（当 $k\gg N$ 时）

空间复杂度

• 存储并查集：$O(N)$
• 总空间：$O(N)$

拓展思考

1. 可视化连通块：可添加DFS/BFS遍历输出每个连通块
2. 动态连根：支持在线查询和更新
3. 区域统计：计算每个连通块的大小和位置

相似题目

1. P3367 【模板】并查集
2. P1197 [JSOI2008] 星球大战
3. P1396 营救