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连B，B连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*1000=1e6，再加一点余量 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）。调试方法：在本地用最大边界值（如m=1000， n=1000）测试，或者检查数组声明的大小。 - 计数错误：最终输出的集合数量不对。原因：
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中维护额外的信息——是相通的。所以，不要小看这道入门题，它是你打开并查集大门，进而探索更广阔算法世界的一块坚实基石。
