以练代学：用竞赛真题学算法—

先上题目，出自蓝桥杯国赛真题

题目描述

w 星球的一个种植园，被分成m 行 n 列的 m×n 个小格子。每个格子里一开始都单独种植了一株合根植物。

这种植物根系很特殊，它的根可以沿着上下左右东西南北四个方向向外延伸，如果两个格子里的植物根系相连、连根在一起，那么这两株植物就会合为一体，变成同一株植物。

现在题目会给出所有连根相连的格子对，我们需要编写程序，计算整个种植园里，最终一共有多少株独立的合根植物。

格子编号规则：从上到下逐行、从左到右依次编号。例如 5 行 4 列的格子，编号依次为：1 2 3 45 6 7 89 10 11 1213 14 15 1617 18 19 20

输入描述

第一行包含两个整数 m、n，表示种植园的行数和列数。第二行包含一个整数 k，表示一共有 k 组合根关系。接下来 k 行，每行两个整数 a、b，表示编号为 a 和编号为 b 的两个格子植物根系相连、合根。

数据范围：1 ≤ m,n ≤ 1000，总格子数不超过 10⁶0 ≤ k ≤ 10⁵

输出描述

输出一个整数，表示整个种植园中最终独立合根植物的总数量。

问题分析

拿到这道题目，很多同学第一反应是用搜索 BFS/DFS 遍历连通块，但仔细分析题目特点就会发现：本题不需要遍历地图，只需要不断合并集合、最后统计集合数量，是一道并查集最标准、最经典、最适合入门的模板原题，也是蓝桥杯每年必考的数据结构。

首先拆解题目核心需求：一开始每个格子都是独立个体，每一株植物自己是一个独立集合；每当两个格子连根，就代表把这两个个体所在的集合合并成同一个集合；最终我们要统计，一共有多少个互不相交的独立集合，也就是独立合根植物数量。

这种动态合并集合、查询是否同一集合、统计集合总数的问题，正是并查集（Union-Find）数据结构的专属应用场景。相比 BFS/DFS，并查集代码更短、效率更高、逻辑更简单，非常适合新手入门。

我们可以得到一个非常简洁的解题思路：

初始化：总植物数量 = 总格子数 m×n，每个格子自己是自己的根；
遍历每一组连根关系 a、b；
查询 a 和 b 是否已经在同一个集合；
如果不在同一个集合，就合并两个集合，同时总植物数量减 1；
全部关系处理完成后，剩余的总数量就是答案。

并查集核心优化是路径压缩，可以让每次查询、合并操作的时间复杂度接近 O (1)，面对 1e5 次操作、1e6 个元素完全不会超时，效率远超暴力搜索。

同时本题没有复杂变形、没有边界坑、没有特殊规则，完全是原生并查集模板，学会这一道，就能掌握并查集 80% 的用法。

代码演示

c++

#include <iostream> using namespace std; const int MAXN = 1005 * 1005; // fa数组：fa[x]表示x的父节点 int fa[MAXN]; // 查找根节点 + 路径压缩核心函数 int find(int x) { if (fa[x] != x) { // 路径压缩：把x直接指向根，缩短路径 fa[x] = find(fa[x]); } return fa[x]; } // 并查集初始化 void init(int total) { for (int i = 1; i <= total; i++) { fa[i] = i; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, n; cin >> m >> n; int total = m * n; // 初始化并查集 init(total); int k; cin >> k; // 初始植物总数=总格子数 int ans = total; for (int i = 0; i < k; i++) { int a, b; cin >> a >> b; // 找到两个点的根 int ra = find(a); int rb = find(b); // 根不同，说明不在同一集合，可以合并 if (ra != rb) { fa[ra] = rb; ans--; } } cout << ans << endl; return 0; }

python

def main(): import sys input = sys.stdin.read().split() ptr = 0 m = int(input[ptr]) ptr += 1 n = int(input[ptr]) ptr += 1 total = m * n # 初始化并查集，下标从1开始 fa = list(range(total + 1)) # 查找+路径压缩 def find(x): if fa[x] != x: fa[x] = find(fa[x]) return fa[x] k = int(input[ptr]) ptr += 1 ans = total for _ in range(k): a = int(input[ptr]) ptr += 1 b = int(input[ptr]) ptr += 1 ra = find(a) rb = find(b) if ra != rb: fa[ra] = rb ans -= 1 print(ans)