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

先上题目出自蓝桥杯国赛真题题目描述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; }pythondef 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)算法详解并查集是由初始化、查找 find、合并 union三个部分组成的数据结构我结合本题一步步详细拆解完全通俗易懂。首先理解并查集原理我们用 fa 数组记录每个元素的父节点每个集合对应一棵树树的最顶端就是根节点。同一个集合内所有元素最终都指向同一个根。第一步初始化每个元素自己是自己的父节点 fa [x]x代表每个元素独立成一个集合对应题目每个格子单独一株植物。第二步 find 查找函数作用是找到 x 所在集合的根节点同时执行路径压缩。路径压缩是并查集灵魂优化递归查找根节点后把沿途所有节点直接指向根把长树压成扁平树后续查询速度会极快几乎是常数时间。第三步合并操作对于一组连根关系 a、b先分别找到它们的根 ra、rb。如果 rarb说明两者已经在同一株植物里无需操作如果 ra≠rb说明是两个不同植物把其中一个根指向另一个根完成合并同时独立植物总数减 1。本题答案统计方式非常巧妙不用最后遍历所有元素统计根数量初始 ans 总格子数每成功合并一次 ans 减 1遍历完所有关系 ans 就是最终独立植物数量时间复杂度最优。并查集时间复杂度是阿克曼函数反函数几乎线性 O (n)处理 m,n≤1000、k≤1e5 完全毫无压力不会超时不会爆内存。同时本题编号从 1 开始不需要处理 0 号边界新手写代码几乎不会出错。结语合根植物是蓝桥杯并查集入门第一题、纯模板原题没有任何陷阱和变形完美覆盖并查集初始化、路径压缩、合并、统计连通块全部核心知识点。