1. 项目概述从“合根植物”到并查集实战看到“合根植物”这个题目很多初次接触的朋友可能会觉得有点抽象甚至联想到生物课。其实在算法竞赛的语境里这是一个非常经典的、用于考察并查集数据结构掌握程度的模型题。它源自蓝桥杯2017年国赛C/C组的真题如今在洛谷等OJ平台上依然活跃是学习并查集不可绕过的入门级练手题。题目描述了一片由 m×n 个格子组成的植物园每个格子种了一株植物这些植物会通过根茎相连形成一个个“合根”的集合。题目会给出若干组已经相连的植物对我们的核心任务就是计算出最后这片植物园里到底有多少个彼此独立的“合根植物”集合。这本质上就是一个连通分量计数问题。想象一下在一片土地上有几滴水银如果让它们相互流动、接触最终会融合成几个独立的大液滴计算这个大液滴的数量就是本题的核心。而并查集正是解决这类“动态连通性”问题最高效的工具之一。它能在近乎常数时间内完成两个元素的“合并”操作以及查询某个元素的“根”代表从而轻松维护和统计集合的数量。对于正在备战蓝桥杯、学习数据结构或者刷题巩固基础的朋友来说透彻理解这道题就等于掌握了并查集最核心的应用场景和代码模板。2. 核心思路与数据结构选型2.1 问题抽象与建模首先我们需要把生动的植物世界抽象成计算机能处理的数据模型。题目给出了网格的行数m和列数n那么总植物数量就是m * n。我们可以给每株植物一个唯一的编号一个很直观的方法是按行优先进行编号第i行第j列的植物编号为(i-1) * n (j-1)或(i-1) * n j取决于下标从0还是1开始通常从1开始更符合题意。这样一个二维网格上的位置就映射到了一个一维的整数ID上方便我们用数组来管理。接下来是关键的“合根”关系。题目会输入k对数字(a, b)表示编号为a和b的植物根茎相连。这里的“相连”具有传递性如果A连BB连C那么A、B、C就属于同一个合根集合。我们的目标就是处理完所有k对连接关系后统计出有多少个互不连通的集合。这立刻让我们联想到图论中的概念每个植物是一个顶点每对连接关系是一条边。统计连通块数量。你可以用DFS/BFS遍历但并查集提供了更优的解决方案尤其是在只需要处理合并与查询而不需要知道连通块内具体连接路径的场景下。2.2 为什么选择并查集面对“动态连通性”和“集合合并与查询”这类问题并查集Union-Find是不二之选。我们来对比一下其他可能的方法深度/广度优先搜索每次查询两个点是否连通或者统计最终连通块数都需要进行一次O(N)的遍历。当合并操作很多时效率低下。维护一个巨大的“所属集合”映射表每次合并两个集合时需要遍历其中一个集合的所有元素修改其所属集合标识。最坏情况下复杂度为O(N^2)。并查集通过两种巧妙的优化将合并与查找的均摊时间复杂度降低到近乎O(1)路径压缩在查找某个元素的根节点时将路径上所有节点的父节点直接指向根。这样树会变得非常扁平后续查找速度极快。按秩合并在合并两棵树时总是将较小的树秩小的根连接到较大的树秩大的根下。这能有效避免树退化成链表。对于本题m和n最大为1000那么植物总数最多可达10^6。k最大可能接近m*n。在这样的数据规模下只有并查集能够保证高效运行。因此选择并查集是基于问题特性和数据规模的必然。3. 并查集实现细节与代码解析3.1 数据结构初始化并查集通常使用一个数组parent[]来实现。parent[i]表示元素i的父节点。初始化时每个元素自成一派所以自己是自己的父节点即parent[i] i。同时我们通常需要另一个数组rank[]或size[]来记录树的“秩”高度或大小用于优化合并操作。对于本题我们还需要一个变量来记录当前集合的数量。初始时集合数等于植物总数total m * n。每次成功合并两个不同的集合集合数量就减1。#include iostream using namespace std; const int MAXN 1000 * 1000 10; // 预留足够空间 int parent[MAXN]; int rank_[MAXN]; // 用rank_避免与STL中的rank冲突 int m, n, k; int setCount; // 当前集合数量 // 初始化并查集 void init() { int total m * n; setCount total; // 初始时每个植物都是一个集合 for (int i 1; i total; i) { parent[i] i; // 自己是自己的父亲 rank_[i] 0; // 初始高度为0 } }注意植物编号从1开始所以我们的数组下标也从1开始使用忽略0号位置这符合题目的一般输入习惯能减少边界判断的麻烦。3.2 查找与路径压缩查找操作find(x)的目的是找到元素x所在集合的“根代表”。朴素实现是不断向上找父亲直到找到根。路径压缩优化是在这个查找过程中将路径上的所有节点都直接挂到根节点下。// 查找根节点带路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归查找并压缩路径 } return parent[x]; }这个递归写法非常简洁。它的作用是如果x不是根parent[x] ! x那么就递归地找到x的根并在回溯的过程中将x的父节点直接设置为根。这样下次再查找x或其路径上的任何节点时速度就会快得多。3.3 合并与按秩合并合并操作unionSet(a, b)是将元素a和b所在的集合合并。首先找到它们的根rootA和rootB。如果根相同说明它们本来就在一个集合里无需操作。如果根不同则需要合并并且集合总数setCount减1。为了保持树的平衡我们采用“按秩合并”。这里“秩”可以理解为树的高度的一个上界。我们总是将秩较小的树的根连接到秩较大的树的根下。// 合并集合带按秩合并 void unionSet(int a, int b) { int rootA find(a); int rootB find(b); if (rootA rootB) return; // 已经在同一集合无需合并 // 按秩合并 if (rank_[rootA] rank_[rootB]) { parent[rootB] rootA; } else if (rank_[rootA] rank_[rootB]) { parent[rootA] rootB; } else { // 秩相等任意合并但被合并的树秩要加1 parent[rootB] rootA; rank_[rootA]; } setCount--; // 成功合并两个不同集合总数减1 }实操心得rank数组的初始值设为0。只有当两棵树高度相同时合并后新树的高度才会增加1。这个优化能有效防止树退化成链状保证find操作的高效。在实际编码中即使不写按秩合并只写路径压缩对于大多数题目也足够了。但加上它能让代码更健壮应对极端数据。3.4 主逻辑与输入处理主函数的逻辑非常清晰读入m,n,k。初始化并查集。循环k次读入一对植物编号a和b调用unionSet(a, b)。输出最终的setCount。int main() { cin m n; cin k; init(); // 初始化并查集 for (int i 0; i k; i) { int a, b; cin a b; unionSet(a, b); // 处理每一组合根关系 } cout setCount endl; // 输出最终合根植物的数量 return 0; }这里有一个关键细节题目没有明确说明编号是否连续、是否在范围内。但根据蓝桥杯和洛谷题目的一般风格以及“植物园格子”的描述我们可以合理推断编号是连续的1到m*n。我们的初始化也是基于这个假设。如果遇到不连续的编号则需要使用离散化技巧但本题不需要。4. 完整代码实现与逐行分析将上述所有部分组合起来就得到了本题的完整AC代码。下面我们贴出完整代码并附上关键行的注释。#include iostream using namespace std; const int MAXN 1000010; // 1000*10001e6再加一点余量 int parent[MAXN]; // 父节点数组 int rank_[MAXN]; // 秩数组 int m, n, k; int setCount; // 当前集合数量 // 初始化并查集 void init() { int total m * n; setCount total; // 初始集合数等于植物总数 for (int i 1; i total; i) { parent[i] i; // 每个节点初始时父节点指向自己 rank_[i] 0; // 初始秩为0 } } // 查找根节点带路径压缩 int find(int x) { // 如果x不是根则递归找到根并设置父节点为根 if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩核心语句 } return parent[x]; } // 合并两个元素所在的集合带按秩合并 void unionSet(int a, int b) { int rootA find(a); int rootB find(b); // 如果根相同说明已经在同一集合直接返回 if (rootA rootB) return; // 按秩合并将秩小的树合并到秩大的树下 if (rank_[rootA] rank_[rootB]) { parent[rootB] rootA; } else if (rank_[rootA] rank_[rootB]) { parent[rootA] rootB; } else { // 秩相等任意合并合并后树的秩加1 parent[rootB] rootA; rank_[rootA]; } // 成功合并两个不同集合集合总数减1 setCount--; } int main() { // 读入行数、列数、连接关系数 cin m n k; // 步骤1初始化并查集 init(); // 步骤2处理所有连接关系 for (int i 0; i k; i) { int a, b; cin a b; unionSet(a, b); // 每输入一对就尝试合并它们所在的集合 } // 步骤3输出最终独立的集合数量 cout setCount endl; return 0; }逐行分析核心部分parent[x] find(parent[x])这是路径压缩的灵魂。它不仅在本次查找中找到了根还一劳永逸地缩短了x及其所有祖先节点下次查找的路径。setCount--这个操作的位置很重要。只有当真地合并了两个不同的集合时才需要减少计数。在unionSet函数中如果发现rootA rootB函数直接返回不会执行setCount--。这确保了计数的准确性。数组大小MAXN这是一个经验值。m和n最大为1000乘积为1,000,000。我们通常习惯开得比最大数据范围稍大一些比如10以防止可能的边界溢出错误这是一个良好的编程习惯。5. 常见问题、调试技巧与扩展思考5.1 典型错误与排查在实现并查集解决本题时新手常会遇到以下几个问题数组越界这是最常犯的错误。如果植物编号从1开始总数为total那么数组大小至少需要total 1。如果你错误地认为编号从0开始或者数组开小了就会发生运行时错误RE。调试方法在本地用最大边界值如m1000 n1000测试或者检查数组声明的大小。计数错误最终输出的集合数量不对。原因setCount的初始值应该是m*n而不是0或别的。并且setCount--必须只在成功合并即两个根不同时执行。调试方法可以用一个小样例如2x2网格1组合根手动模拟打印出每一步的parent数组和setCount值。TLE时间超限如果使用了没有优化的并查集朴素的查找和合并在数据量大时可能会超时。解决方案务必实现路径压缩和按秩合并。本题的数据规模下优化后的并查集完全可以在规定时间内完成。输入格式理解错误题目是先输入m和n再输入k。有些同学可能会错误地认为是一行输入三个数。务必严格按照题目描述的格式读取。5.2 并查集的其他优化与变种除了标准的路径压缩和按秩合并并查集还有一些有趣的变种在解决特定问题时非常有用按大小合并用size[]数组记录每个集合的元素个数合并时将小集合合并到大集合。这与按秩合并思想类似有时能更方便地获取集合大小信息。带权并查集在维护父子关系的同时还维护每个节点到根节点的某种“权值”如距离、差值等。常用于解决诸如“食物链”、“奇偶游戏”等需要传递关系的复杂问题。可撤销并查集记录合并操作的历史支持回退到之前的某个状态。常用于需要离线处理、分治或回溯的场景。对于“合根植物”这道题标准并查集已经足够。但了解这些扩展能帮助你在遇到更复杂的问题时知道该往哪个方向思考。5.3 从本题出发的扩展思考掌握本题后你可以尝试用同样的思路去解决一系列相似问题达到举一反三的效果洛谷P1551 亲戚最纯粹的并查集模板题直接判断两个人是否属于同一个家族。洛谷P1111 修复公路本质是求将所有点连通的最小时间可以按时间排序边后用并查集合并当集合数变为1时的时间即为答案。连通块计数问题例如在二维字符矩阵中统计‘1’构成的连通块数量八方向或四方向。你可以将每个‘1’的位置映射为一个唯一编号然后将相邻的‘1’用并查集合并最后统计集合数。这比BFS/DFS更节省空间且易于理解。判断图中是否有环在逐步加边的过程中如果准备加入的边连接的两个顶点已经在同一个集合中那么加入这条边就会形成环。我个人在最初学习并查集时“合根植物”这道题给了我很大的信心。它模型简单输入输出清晰完美展现了并查集“维护连通性”和“统计集合数量”两大核心功能。把这里的代码模板理解、背熟再结合路径压缩和按秩合并的优化思想你就能解决一大类基础图论连通性问题。在后续遇到更复杂的带权并查集时也会发现其核心思想——在find和union中维护额外的信息——是相通的。所以不要小看这道入门题它是你打开并查集大门进而探索更广阔算法世界的一块坚实基石。