1. 项目概述从“团伙”问题看并查集的核心应用最近在带学生刷《信息学奥赛一本通》的题目做到1385题“团伙(group)”时发现这真是一道理解并查集Union-Find数据结构的绝佳例题。很多刚接触算法的同学一听到“并查集”就觉得抽象但“团伙”这个生活化的场景恰恰能把它的原理讲得明明白白。这道题本质上是一个经典的“朋友的朋友是朋友敌人的敌人也是朋友”的逻辑推理问题用并查集来维护这种复杂的关系网络效率高且代码简洁。如果你正在学习C和数据结构或者备战信息学奥赛搞懂这道题就能掌握并查集解决实际问题的核心套路。接下来我就结合自己多年的刷题和教学经验把这道题的解题思路、代码实现细节以及常见的坑点掰开揉碎了讲给你听。2. 问题核心与并查集思想拆解2.1 题目场景还原与需求分析我们先来把题目翻译成“人话”。题目大意是有n个人编号从1到n。他们之间有两种关系E p q表示p和q是敌人Enemy。F p q表示p和q是朋友Friend。然后题目给出了一个关键的公理也是我们解题的逻辑基础朋友关系具有传递性如果A是B的朋友B是C的朋友那么A和C也是朋友。这很好理解你的朋友的朋友自然也是你的朋友圈里的人。“敌人的敌人是朋友”这是本题的精华也是容易绕晕的地方。如果A和B是敌人B和C也是敌人那么A和C就成了朋友。这有点像武侠小说里“共同的敌人让我们站在了同一战线”。题目最终问的是根据给定的所有关系这n个人最终会形成多少个互不相交的“团伙”这里的“团伙”就是一个极大的连通群体群体内的人要么直接是朋友要么通过朋友关系或“敌人的敌人”规则间接成为朋友。需求拆解我们需要一个数据结构能高效地完成两件事合并Union当确定两个人属于同一个团伙时将他们的集合合并。查询Find快速判断任意两个人是否属于同一个团伙。这不正是并查集的看家本领吗但难点在于如何用并查集来处理“敌人”这种对立关系并推导出“敌人的敌人是朋友”这条规则。2.2 并查集方案选型与“扩展域”思想最朴素的想法是只用一个并查集遇到朋友就合并。但敌人关系怎么存存了又怎么体现“敌人的敌人是朋友”这里就需要引入一个非常巧妙的思路扩展域并查集也叫种类并查集。它的核心思想是“拆点”把一个实体拆分成多个逻辑上的点分别代表它处于不同“种类”或“状态”下的身份。对于本题我们为每个人i创建两个逻辑点i代表“i是朋友域”的身份。可以理解为i的“朋友化身”。i n代表“i是敌人域”的身份。可以理解为i的“敌人化身”。这里n是总人数保证编号不重叠这个“域”怎么理解呢它不是一个实际存在的人而是一个关系标签。i和in本身没有直接关系。它们的作用是通过与其他人的“化身”建立连接来编码复杂的关系。规则翻译成并查集操作F p q(p和q是朋友)这意味着p的“朋友化身”和q的“朋友化身”应该在同一个集合。同时逻辑上推理如果p和q是朋友那么p的敌人也应该是q的敌人。所以p的“敌人化身”和q的“敌人化身”也应该在同一个集合。操作union(p, q)和union(pn, qn)。E p q(p和q是敌人)这意味着p的“朋友化身”和q的“敌人化身”应该在同一个集合。为什么因为“敌人”关系可以理解为我的朋友域和你的敌人域是同一阵营的。换句话说p的朋友圈就是q的敌对面。同理q的“朋友化身”和p的“敌人化身”也应在同一个集合。操作union(p, qn)和union(q, pn)。“敌人的敌人是朋友”如何自动实现这是最精妙的部分。假设我们有关系E 1 2和E 2 3。执行E 1 2:union(1, 2n),union(2, 1n)。此时1的朋友域和2的敌人域连通2的朋友域和1的敌人域连通。执行E 2 3:union(2, 3n),union(3, 2n)。此时2的朋友域和3的敌人域连通3的朋友域和2的敌人域连通。现在来看1和3的关系1的朋友域节点1连接着2的敌人域节点2n而2的敌人域节点2n又通过第二次操作union(2, 3n)连接着3的敌人域节点3n等等这里需要仔细追踪。 实际上union(2, 3n)是把2的朋友域和3的敌人域连在了一起。而1的朋友域连着的是2的敌人域节点2n。2的朋友域和2的敌人域之间并没有直接连接。让我们通过并查集的树结构来思考执行完两个E操作后我们可能有这样的连接简化表示Find(1) Find(2n)// 来自 E 1 2Find(2) Find(3n)// 来自 E 2 3Find(2) Find(1n)// 来自 E 1 2Find(3) Find(2n)// 来自 E 2 3现在检查Find(1) Find(3)是否成立Find(1)指向2n。Find(3)指向2n(因为Find(3) Find(2n)而Find(2n)在第一次操作中就是2n的根)。 所以Find(1) Find(3)成立这意味着1的朋友域和3的朋友域在同一个集合里即1和3是朋友。整个推导过程由并查集在合并操作中自动完成我们不需要写额外的判断逻辑。注意这里的关键是pn这个点并不代表“某个人”它只代表“p的敌人身份”这个抽象概念。当union(p, qn)时意思是“p的朋友阵营”和“q的敌人阵营”合并了从而隐式地编码了所有关系。2.3 基础并查集实现选型路径压缩与按秩合并确定了使用扩展域2倍大小的并查集后我们需要实现一个高效的并查集。通常我们会采用“路径压缩 按秩合并”来优化使Find和Union操作的平均时间复杂度接近常数级。父节点数组vectorint parent(2*n1)。parent[i]表示节点i的父节点。初始化时parent[i] i。秩数组可选但推荐vectorint rank(2*n1, 0)。rank[i]表示以i为根的树的近似高度。用于在Union时决定将哪棵树的根作为新根避免树退化成链表。核心操作Find(x)查找x所在集合的根代表元。递归或迭代地向上找同时将路径上所有节点的父节点直接指向根路径压缩。int find(int x, vectorint parent) { if (parent[x] ! x) { parent[x] find(parent[x], parent); // 递归路径压缩 } return parent[x]; } // 迭代版本同样常用 int find(int x, vectorint parent) { int root x; while (parent[root] ! root) root parent[root]; // 找到根 // 路径压缩 while (x ! root) { int next parent[x]; parent[x] root; x next; } return root; }Union(x, y)合并x和y所在的集合。先找到它们的根rootX和rootY如果不同根则将一棵树挂到另一棵树下。按秩合并是选择将秩较小的树挂到秩较大的树下如果秩相等则任选一个作为新根并将其秩加1。void unionSets(int x, int y, vectorint parent, vectorint rank) { int rootX find(x, parent); int rootY find(y, parent); if (rootX ! rootY) { if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } } }对于本题由于我们提前知道所有操作先读入所有关系再处理且n通常不会巨大一般1000即使不使用按秩合并只使用路径压缩性能也完全足够。但养成好习惯写出优化版本总是更稳妥。3. 代码实现与逐行解析理解了原理我们来看完整的C代码实现。我会将代码分成几个部分并加上详细注释。3.1 数据结构定义与初始化#include iostream #include vector using namespace std; class UnionFind { private: vectorint parent; vectorint rank; // 按秩合并的秩数组 int n; // 人数 public: // 构造函数初始化大小为 2*n (朋友域和敌人域) UnionFind(int size) : n(size) { int totalSize 2 * size 1; // 索引从1开始多开一点空间 parent.resize(totalSize); rank.resize(totalSize, 0); // 初始化每个元素的父节点为自己 for (int i 1; i totalSize; i) { parent[i] i; } } // 查找操作带路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归压缩路径 } return parent[x]; } // 合并操作带按秩合并 void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 已在同一集合 // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } } // 判断x和y是否在同一集合 bool isConnected(int x, int y) { return find(x) find(y); } };关键点说明数组大小是2 * n 1。因为人有n个每个人有朋友域和敌人域两个逻辑点所以总共2*n个点。1是为了让下标从1开始更直观人的编号是1~n。rank数组初始化为0。在按秩合并时秩可以理解为树高的上界。find函数使用递归实现路径压缩代码简洁。对于特别深的树本题不会递归可能有栈溢出风险但通常没问题。迭代版本更安全。unite函数中如果两个根节点的秩不同将秩小的树合并到秩大的树下这样不会增加整体树高。如果秩相同合并后新根的秩需要加1。3.2 主逻辑关系处理与团伙计数int main() { int n, m; cin n m; // n个人m条关系 UnionFind uf(n); for (int i 0; i m; i) { char op; int p, q; cin op p q; if (op F) { // 朋友关系合并朋友域合并敌人域 uf.unite(p, q); uf.unite(p n, q n); } else if (op E) { // 敌人关系p的朋友域与q的敌人域合并q的朋友域与p的敌人域合并 uf.unite(p, q n); uf.unite(q, p n); } }关系处理逻辑这部分直接对应了前面讲的规则翻译。它是整个算法的核心代码非常简洁但背后是扩展域思想的支撑。每读入一条关系就进行两次合并操作将对应的逻辑点连接起来。3.3 统计最终团伙数量这是最后一步也是容易出错的一步。我们需要统计有多少个不同的“团伙”。一个团伙对应并查集里的一个连通集合。但注意我们的并查集里有2*n个点逻辑点我们只关心原始n个人即编号1到n的朋友域所在的连通块数量。// 统计团伙数量 vectorbool isRoot(n 1, false); // 标记某个根是否已被计数 int gangCount 0; for (int i 1; i n; i) { int root uf.find(i); // 查找第i个人的朋友域的根 if (!isRoot[root]) { isRoot[root] true; gangCount; } } cout gangCount endl; return 0; }统计逻辑解析我们只遍历i 1到n这对应着每个人的“朋友化身”。in的敌人域我们不关心因为它只是用于推导关系的辅助点。uf.find(i)找到第i个人的朋友域所在的集合的根。使用一个布尔数组isRoot来记录哪些根已经被计数过。同一个集合的所有点find出来的根是相同的我们只对每个根计数一次。最终gangCount就是互不相交的团伙数量。实操心得这里isRoot数组的大小设为n1是不够严谨但通常可行的。因为find(i)返回的根节点编号可能是1到2*n之间的任何数。一个更安全的做法是将其大小设为2*n1或者使用unordered_setint来存储根。但在实际竞赛中由于我们只关心1到n的点的根并且这些根也必然在1到2n之间开一个2*n1大小的布尔数组是更稳妥的选择。我上面的代码为了清晰展示逻辑使用了n1在已知数据范围下通常能AC但严格来说应使用2*n1。4. 完整代码与测试用例将以上所有部分组合起来得到完整AC代码#include iostream #include vector using namespace std; class UnionFind { private: vectorint parent; vectorint rank; int n; public: UnionFind(int size) : n(size) { int totalSize 2 * size 1; parent.resize(totalSize); rank.resize(totalSize, 0); for (int i 1; i totalSize; i) { parent[i] i; } } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } } bool isConnected(int x, int y) { return find(x) find(y); } }; int main() { int n, m; cin n m; UnionFind uf(n); for (int i 0; i m; i) { char op; int p, q; cin op p q; if (op F) { uf.unite(p, q); uf.unite(p n, q n); } else if (op E) { uf.unite(p, q n); uf.unite(q, p n); } } // 更安全的根统计方式 vectorbool isRoot(2 * n 1, false); int gangCount 0; for (int i 1; i n; i) { int root uf.find(i); if (!isRoot[root]) { isRoot[root] true; gangCount; } } cout gangCount endl; return 0; }测试用例验证 我们用一个经典的例子来验证算法逻辑。 输入6 4 E 1 2 E 2 3 F 1 4 E 4 5推导过程E 1 2: 合并(1, 2n), (2, 1n)。集合情况开始复杂化。E 2 3: 合并(2, 3n), (3, 2n)。此时通过并查集的传递性1和3的朋友域连通成为朋友。F 1 4: 合并(1, 4), (1n, 4n)。由于1和3已是朋友这间接使3和4也成为朋友。E 4 5: 合并(4, 5n), (5, 4n)。由于4和1、3是朋友根据“敌人的敌人是朋友”5会成为1和3的敌人吗不这条规则不直接作用于“朋友的朋友的敌人”。我们需要看最终连通性。 让我们手动追踪关键关系经过所有操作后find(1)、find(3)、find(4)的根应该相同他们在同一个朋友团伙。find(2)的根呢它通过E 1 2中的union(2, 1n)连接到了1的敌人域。find(5)的根通过E 4 5中的union(5, 4n)连接到了4的敌人域。而4的敌人域(4n)通过F 1 4中的union(1n, 4n)连接到了1的敌人域(1n)。所以find(2)和find(5)的根都指向了与1的敌人域相关的集合但find(2)和find(5)的根是否相同find(2)直接连到1n。find(5)连到4n而4n的根是1n(因为union(1n, 4n))。所以find(2) find(5)即2和5在同一个集合都是1所在团伙的敌人不他们属于另一个团伙。仔细分析2和5都是通过“某人的敌人域”联系在一起的他们自己的朋友域形成了一个独立的团伙吗统计时我们只统计i (1in)的朋友域的根。对于i2find(2)的根是1n(一个敌人域节点)。对于i5find(5)的根也是1n。所以2和5的朋友域在同一个集合。而1、3、4的朋友域在另一个集合根是1。此外6没有与任何人建立关系自成一个集合。 所以最终团伙应该是3个{1,3,4}, {2,5}, {6}。程序输出应为3。运行上述代码输入测试用例输出为3符合预期。5. 常见问题、调试技巧与扩展思考5.1 为什么数组要开2*n1这是新手最容易犯的错。因为每个人有两个逻辑点i和in。当i n时in 2n。所以数组下标至少要能访问到2n。我们通常习惯开2*n 1或2*n 10让下标从1开始并且留有一点余量防止粗心导致的越界。如果只开n1在访问parent[pn]时必然越界导致程序崩溃或结果错误。5.2 “敌人的敌人是朋友”规则在处理E关系时已经体现了吗是的完全体现了。这是扩展域并查集最精妙的地方。我们没有在代码中显式地写任何逻辑来判断“如果A和B是敌人B和C是敌人那么合并A和C”。这个推导过程是由并查集数据结构在多次union操作中自动完成的如第2.2节所演示的。我们只需要忠实地按照“朋友合并朋友域和敌人域”、“敌人交叉合并”的规则去union剩下的推理就交给并查集的连通性。5.3 能否用更小的空间比如只开n1的数组有一种称为“带权并查集”或“关系并查集”的方法可以在一个大小为n的并查集内通过维护每个节点到根节点的“关系”如0表示同类1表示异类来解决此类问题。它更省空间但思维难度和代码复杂度更高容易在关系转移时出错。对于“团伙”这类题目扩展域2倍空间的思路更直观更不容易错是竞赛中的首选方法。在内存充裕的情况下n 1000或10000优先选择思路清晰的解法。5.4 调试技巧如何验证自己的并查集操作是否正确当结果不对时可以添加调试输出打印父节点数组在每次union操作后打印出parent[1..2n]的变化观察连通情况。小数据手工模拟就像我上面测试用例做的那样用纸笔跟踪几个人的关系变化画出并查集的树状图验证find操作的结果是否符合预期。单元测试编写几个简单的测试函数检查find和union的基本功能。例如初始化后find(i)iunion(1,2)后find(1)find(2)。5.5 扩展思考如果关系更多样呢“团伙”题是并查集处理复杂关系的入门题。现实中关系可能更复杂比如三种关系朋友、敌人、中立。带权关系关系的强度或可信度。动态关系关系会随时间改变或撤销。对于更复杂的情况可能需要更多扩展域如果有k种关系可以扩展为k倍大小。带权并查集维护更复杂的关系权值向量。可撤销并查集使用栈记录操作历史支持回退。但万变不离其宗核心思想都是用并查集的连通性来编码和推导实体间的逻辑关系。5.6 性能考量与优化本题的典型数据范围是n 1000, m 5000。我们的算法时间复杂度约为O(m * α(n))其中α是反阿克曼函数增长极慢可以视为常数。因此完全可以在时限内通过。即使n大到10^5级别并查集也游刃有余。最后的建议理解并查集的关键在于多画图。把每个点、每次合并操作后的集合状态画出来亲眼看到“朋友的传递”和“敌人的敌人是朋友”是如何通过简单的union操作涌现出来的这种顿悟感是只看代码无法获得的。把这道“团伙”题吃透并查集的大门就算真正打开了。
1. 项目概述从“团伙”问题看并查集的核心应用最近在带学生刷《信息学奥赛一本通》的题目做到1385题“团伙(group)”时发现这真是一道理解并查集Union-Find数据结构的绝佳例题。很多刚接触算法的同学一听到“并查集”就觉得抽象但“团伙”这个生活化的场景恰恰能把它的原理讲得明明白白。这道题本质上是一个经典的“朋友的朋友是朋友敌人的敌人也是朋友”的逻辑推理问题用并查集来维护这种复杂的关系网络效率高且代码简洁。如果你正在学习C和数据结构或者备战信息学奥赛搞懂这道题就能掌握并查集解决实际问题的核心套路。接下来我就结合自己多年的刷题和教学经验把这道题的解题思路、代码实现细节以及常见的坑点掰开揉碎了讲给你听。2. 问题核心与并查集思想拆解2.1 题目场景还原与需求分析我们先来把题目翻译成“人话”。题目大意是有n个人编号从1到n。他们之间有两种关系E p q表示p和q是敌人Enemy。F p q表示p和q是朋友Friend。然后题目给出了一个关键的公理也是我们解题的逻辑基础朋友关系具有传递性如果A是B的朋友B是C的朋友那么A和C也是朋友。这很好理解你的朋友的朋友自然也是你的朋友圈里的人。“敌人的敌人是朋友”这是本题的精华也是容易绕晕的地方。如果A和B是敌人B和C也是敌人那么A和C就成了朋友。这有点像武侠小说里“共同的敌人让我们站在了同一战线”。题目最终问的是根据给定的所有关系这n个人最终会形成多少个互不相交的“团伙”这里的“团伙”就是一个极大的连通群体群体内的人要么直接是朋友要么通过朋友关系或“敌人的敌人”规则间接成为朋友。需求拆解我们需要一个数据结构能高效地完成两件事合并Union当确定两个人属于同一个团伙时将他们的集合合并。查询Find快速判断任意两个人是否属于同一个团伙。这不正是并查集的看家本领吗但难点在于如何用并查集来处理“敌人”这种对立关系并推导出“敌人的敌人是朋友”这条规则。2.2 并查集方案选型与“扩展域”思想最朴素的想法是只用一个并查集遇到朋友就合并。但敌人关系怎么存存了又怎么体现“敌人的敌人是朋友”这里就需要引入一个非常巧妙的思路扩展域并查集也叫种类并查集。它的核心思想是“拆点”把一个实体拆分成多个逻辑上的点分别代表它处于不同“种类”或“状态”下的身份。对于本题我们为每个人i创建两个逻辑点i代表“i是朋友域”的身份。可以理解为i的“朋友化身”。i n代表“i是敌人域”的身份。可以理解为i的“敌人化身”。这里n是总人数保证编号不重叠这个“域”怎么理解呢它不是一个实际存在的人而是一个关系标签。i和in本身没有直接关系。它们的作用是通过与其他人的“化身”建立连接来编码复杂的关系。规则翻译成并查集操作F p q(p和q是朋友)这意味着p的“朋友化身”和q的“朋友化身”应该在同一个集合。同时逻辑上推理如果p和q是朋友那么p的敌人也应该是q的敌人。所以p的“敌人化身”和q的“敌人化身”也应该在同一个集合。操作union(p, q)和union(pn, qn)。E p q(p和q是敌人)这意味着p的“朋友化身”和q的“敌人化身”应该在同一个集合。为什么因为“敌人”关系可以理解为我的朋友域和你的敌人域是同一阵营的。换句话说p的朋友圈就是q的敌对面。同理q的“朋友化身”和p的“敌人化身”也应在同一个集合。操作union(p, qn)和union(q, pn)。“敌人的敌人是朋友”如何自动实现这是最精妙的部分。假设我们有关系E 1 2和E 2 3。执行E 1 2:union(1, 2n),union(2, 1n)。此时1的朋友域和2的敌人域连通2的朋友域和1的敌人域连通。执行E 2 3:union(2, 3n),union(3, 2n)。此时2的朋友域和3的敌人域连通3的朋友域和2的敌人域连通。现在来看1和3的关系1的朋友域节点1连接着2的敌人域节点2n而2的敌人域节点2n又通过第二次操作union(2, 3n)连接着3的敌人域节点3n等等这里需要仔细追踪。 实际上union(2, 3n)是把2的朋友域和3的敌人域连在了一起。而1的朋友域连着的是2的敌人域节点2n。2的朋友域和2的敌人域之间并没有直接连接。让我们通过并查集的树结构来思考执行完两个E操作后我们可能有这样的连接简化表示Find(1) Find(2n)// 来自 E 1 2Find(2) Find(3n)// 来自 E 2 3Find(2) Find(1n)// 来自 E 1 2Find(3) Find(2n)// 来自 E 2 3现在检查Find(1) Find(3)是否成立Find(1)指向2n。Find(3)指向2n(因为Find(3) Find(2n)而Find(2n)在第一次操作中就是2n的根)。 所以Find(1) Find(3)成立这意味着1的朋友域和3的朋友域在同一个集合里即1和3是朋友。整个推导过程由并查集在合并操作中自动完成我们不需要写额外的判断逻辑。注意这里的关键是pn这个点并不代表“某个人”它只代表“p的敌人身份”这个抽象概念。当union(p, qn)时意思是“p的朋友阵营”和“q的敌人阵营”合并了从而隐式地编码了所有关系。2.3 基础并查集实现选型路径压缩与按秩合并确定了使用扩展域2倍大小的并查集后我们需要实现一个高效的并查集。通常我们会采用“路径压缩 按秩合并”来优化使Find和Union操作的平均时间复杂度接近常数级。父节点数组vectorint parent(2*n1)。parent[i]表示节点i的父节点。初始化时parent[i] i。秩数组可选但推荐vectorint rank(2*n1, 0)。rank[i]表示以i为根的树的近似高度。用于在Union时决定将哪棵树的根作为新根避免树退化成链表。核心操作Find(x)查找x所在集合的根代表元。递归或迭代地向上找同时将路径上所有节点的父节点直接指向根路径压缩。int find(int x, vectorint parent) { if (parent[x] ! x) { parent[x] find(parent[x], parent); // 递归路径压缩 } return parent[x]; } // 迭代版本同样常用 int find(int x, vectorint parent) { int root x; while (parent[root] ! root) root parent[root]; // 找到根 // 路径压缩 while (x ! root) { int next parent[x]; parent[x] root; x next; } return root; }Union(x, y)合并x和y所在的集合。先找到它们的根rootX和rootY如果不同根则将一棵树挂到另一棵树下。按秩合并是选择将秩较小的树挂到秩较大的树下如果秩相等则任选一个作为新根并将其秩加1。void unionSets(int x, int y, vectorint parent, vectorint rank) { int rootX find(x, parent); int rootY find(y, parent); if (rootX ! rootY) { if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } } }对于本题由于我们提前知道所有操作先读入所有关系再处理且n通常不会巨大一般1000即使不使用按秩合并只使用路径压缩性能也完全足够。但养成好习惯写出优化版本总是更稳妥。3. 代码实现与逐行解析理解了原理我们来看完整的C代码实现。我会将代码分成几个部分并加上详细注释。3.1 数据结构定义与初始化#include iostream #include vector using namespace std; class UnionFind { private: vectorint parent; vectorint rank; // 按秩合并的秩数组 int n; // 人数 public: // 构造函数初始化大小为 2*n (朋友域和敌人域) UnionFind(int size) : n(size) { int totalSize 2 * size 1; // 索引从1开始多开一点空间 parent.resize(totalSize); rank.resize(totalSize, 0); // 初始化每个元素的父节点为自己 for (int i 1; i totalSize; i) { parent[i] i; } } // 查找操作带路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归压缩路径 } return parent[x]; } // 合并操作带按秩合并 void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 已在同一集合 // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } } // 判断x和y是否在同一集合 bool isConnected(int x, int y) { return find(x) find(y); } };关键点说明数组大小是2 * n 1。因为人有n个每个人有朋友域和敌人域两个逻辑点所以总共2*n个点。1是为了让下标从1开始更直观人的编号是1~n。rank数组初始化为0。在按秩合并时秩可以理解为树高的上界。find函数使用递归实现路径压缩代码简洁。对于特别深的树本题不会递归可能有栈溢出风险但通常没问题。迭代版本更安全。unite函数中如果两个根节点的秩不同将秩小的树合并到秩大的树下这样不会增加整体树高。如果秩相同合并后新根的秩需要加1。3.2 主逻辑关系处理与团伙计数int main() { int n, m; cin n m; // n个人m条关系 UnionFind uf(n); for (int i 0; i m; i) { char op; int p, q; cin op p q; if (op F) { // 朋友关系合并朋友域合并敌人域 uf.unite(p, q); uf.unite(p n, q n); } else if (op E) { // 敌人关系p的朋友域与q的敌人域合并q的朋友域与p的敌人域合并 uf.unite(p, q n); uf.unite(q, p n); } }关系处理逻辑这部分直接对应了前面讲的规则翻译。它是整个算法的核心代码非常简洁但背后是扩展域思想的支撑。每读入一条关系就进行两次合并操作将对应的逻辑点连接起来。3.3 统计最终团伙数量这是最后一步也是容易出错的一步。我们需要统计有多少个不同的“团伙”。一个团伙对应并查集里的一个连通集合。但注意我们的并查集里有2*n个点逻辑点我们只关心原始n个人即编号1到n的朋友域所在的连通块数量。// 统计团伙数量 vectorbool isRoot(n 1, false); // 标记某个根是否已被计数 int gangCount 0; for (int i 1; i n; i) { int root uf.find(i); // 查找第i个人的朋友域的根 if (!isRoot[root]) { isRoot[root] true; gangCount; } } cout gangCount endl; return 0; }统计逻辑解析我们只遍历i 1到n这对应着每个人的“朋友化身”。in的敌人域我们不关心因为它只是用于推导关系的辅助点。uf.find(i)找到第i个人的朋友域所在的集合的根。使用一个布尔数组isRoot来记录哪些根已经被计数过。同一个集合的所有点find出来的根是相同的我们只对每个根计数一次。最终gangCount就是互不相交的团伙数量。实操心得这里isRoot数组的大小设为n1是不够严谨但通常可行的。因为find(i)返回的根节点编号可能是1到2*n之间的任何数。一个更安全的做法是将其大小设为2*n1或者使用unordered_setint来存储根。但在实际竞赛中由于我们只关心1到n的点的根并且这些根也必然在1到2n之间开一个2*n1大小的布尔数组是更稳妥的选择。我上面的代码为了清晰展示逻辑使用了n1在已知数据范围下通常能AC但严格来说应使用2*n1。4. 完整代码与测试用例将以上所有部分组合起来得到完整AC代码#include iostream #include vector using namespace std; class UnionFind { private: vectorint parent; vectorint rank; int n; public: UnionFind(int size) : n(size) { int totalSize 2 * size 1; parent.resize(totalSize); rank.resize(totalSize, 0); for (int i 1; i totalSize; i) { parent[i] i; } } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } } bool isConnected(int x, int y) { return find(x) find(y); } }; int main() { int n, m; cin n m; UnionFind uf(n); for (int i 0; i m; i) { char op; int p, q; cin op p q; if (op F) { uf.unite(p, q); uf.unite(p n, q n); } else if (op E) { uf.unite(p, q n); uf.unite(q, p n); } } // 更安全的根统计方式 vectorbool isRoot(2 * n 1, false); int gangCount 0; for (int i 1; i n; i) { int root uf.find(i); if (!isRoot[root]) { isRoot[root] true; gangCount; } } cout gangCount endl; return 0; }测试用例验证 我们用一个经典的例子来验证算法逻辑。 输入6 4 E 1 2 E 2 3 F 1 4 E 4 5推导过程E 1 2: 合并(1, 2n), (2, 1n)。集合情况开始复杂化。E 2 3: 合并(2, 3n), (3, 2n)。此时通过并查集的传递性1和3的朋友域连通成为朋友。F 1 4: 合并(1, 4), (1n, 4n)。由于1和3已是朋友这间接使3和4也成为朋友。E 4 5: 合并(4, 5n), (5, 4n)。由于4和1、3是朋友根据“敌人的敌人是朋友”5会成为1和3的敌人吗不这条规则不直接作用于“朋友的朋友的敌人”。我们需要看最终连通性。 让我们手动追踪关键关系经过所有操作后find(1)、find(3)、find(4)的根应该相同他们在同一个朋友团伙。find(2)的根呢它通过E 1 2中的union(2, 1n)连接到了1的敌人域。find(5)的根通过E 4 5中的union(5, 4n)连接到了4的敌人域。而4的敌人域(4n)通过F 1 4中的union(1n, 4n)连接到了1的敌人域(1n)。所以find(2)和find(5)的根都指向了与1的敌人域相关的集合但find(2)和find(5)的根是否相同find(2)直接连到1n。find(5)连到4n而4n的根是1n(因为union(1n, 4n))。所以find(2) find(5)即2和5在同一个集合都是1所在团伙的敌人不他们属于另一个团伙。仔细分析2和5都是通过“某人的敌人域”联系在一起的他们自己的朋友域形成了一个独立的团伙吗统计时我们只统计i (1in)的朋友域的根。对于i2find(2)的根是1n(一个敌人域节点)。对于i5find(5)的根也是1n。所以2和5的朋友域在同一个集合。而1、3、4的朋友域在另一个集合根是1。此外6没有与任何人建立关系自成一个集合。 所以最终团伙应该是3个{1,3,4}, {2,5}, {6}。程序输出应为3。运行上述代码输入测试用例输出为3符合预期。5. 常见问题、调试技巧与扩展思考5.1 为什么数组要开2*n1这是新手最容易犯的错。因为每个人有两个逻辑点i和in。当i n时in 2n。所以数组下标至少要能访问到2n。我们通常习惯开2*n 1或2*n 10让下标从1开始并且留有一点余量防止粗心导致的越界。如果只开n1在访问parent[pn]时必然越界导致程序崩溃或结果错误。5.2 “敌人的敌人是朋友”规则在处理E关系时已经体现了吗是的完全体现了。这是扩展域并查集最精妙的地方。我们没有在代码中显式地写任何逻辑来判断“如果A和B是敌人B和C是敌人那么合并A和C”。这个推导过程是由并查集数据结构在多次union操作中自动完成的如第2.2节所演示的。我们只需要忠实地按照“朋友合并朋友域和敌人域”、“敌人交叉合并”的规则去union剩下的推理就交给并查集的连通性。5.3 能否用更小的空间比如只开n1的数组有一种称为“带权并查集”或“关系并查集”的方法可以在一个大小为n的并查集内通过维护每个节点到根节点的“关系”如0表示同类1表示异类来解决此类问题。它更省空间但思维难度和代码复杂度更高容易在关系转移时出错。对于“团伙”这类题目扩展域2倍空间的思路更直观更不容易错是竞赛中的首选方法。在内存充裕的情况下n 1000或10000优先选择思路清晰的解法。5.4 调试技巧如何验证自己的并查集操作是否正确当结果不对时可以添加调试输出打印父节点数组在每次union操作后打印出parent[1..2n]的变化观察连通情况。小数据手工模拟就像我上面测试用例做的那样用纸笔跟踪几个人的关系变化画出并查集的树状图验证find操作的结果是否符合预期。单元测试编写几个简单的测试函数检查find和union的基本功能。例如初始化后find(i)iunion(1,2)后find(1)find(2)。5.5 扩展思考如果关系更多样呢“团伙”题是并查集处理复杂关系的入门题。现实中关系可能更复杂比如三种关系朋友、敌人、中立。带权关系关系的强度或可信度。动态关系关系会随时间改变或撤销。对于更复杂的情况可能需要更多扩展域如果有k种关系可以扩展为k倍大小。带权并查集维护更复杂的关系权值向量。可撤销并查集使用栈记录操作历史支持回退。但万变不离其宗核心思想都是用并查集的连通性来编码和推导实体间的逻辑关系。5.6 性能考量与优化本题的典型数据范围是n 1000, m 5000。我们的算法时间复杂度约为O(m * α(n))其中α是反阿克曼函数增长极慢可以视为常数。因此完全可以在时限内通过。即使n大到10^5级别并查集也游刃有余。最后的建议理解并查集的关键在于多画图。把每个点、每次合并操作后的集合状态画出来亲眼看到“朋友的传递”和“敌人的敌人是朋友”是如何通过简单的union操作涌现出来的这种顿悟感是只看代码无法获得的。把这道“团伙”题吃透并查集的大门就算真正打开了。
