考场上看到“JZOJ3875”这串编号再扫一眼“NOIP2014八校联考”“星球联盟(alliance)”我第一反应是完了这八成又是一道带星际背景的期望题或者树上难题。结果硬着头皮读完题面才发现它讲的是几个星球之间建立航道、合并联盟的故事剥掉那层科幻皮内核就是一个非常经典的并查集维护连通块大小。更巧的是这道题的想法一点都不偏反而是那种“你明明会并查集却容易在题意理解上栽跟头”的题。这类题在联考里属于典型的“保分题”但它的坑也不少很值得写一篇复盘。最近又在辅导群里看到有人问这道题的解法我才意识到很多同学卡住的地方并不是算法本身而是几个非常隐蔽的细节初始边和提案边怎么处理、两个星球已经在同一个联盟时答案到底输出什么、以及为什么不能用DFS暴力。这篇文章我就从这几个角度完整拆一遍顺带把代码、易错点和排查思路都放在一起供准备NOIP和联赛的同学参考。如果你已经把并查集玩得比较熟可以直接跳到第4节看代码细节如果是刚学到并查集建议从头到尾按顺序读一遍。1. 题目到底在讲什么1.1 披着科幻外衣的连通性问题先聊题面。故事背景大概是这样的宇宙里有若干颗星球编号从1到N。最初有一部分星球之间已经修好了双向航道也就是说它们可以直接往来并且通过航道网连在一起。凡是彼此连通的星球就会自动形成一个“联盟”。联盟不是一个独立的势力它本质上就是“连通的点集”。接下来会按顺序出现P个提案每个提案包含两个星球u和v表示计划在它们之间新建一条航道。每次提案出现后我们都要当场判断如果这两个星球目前不在同一个联盟那么新航道一旦建成两个联盟就会合并成一个更大的联盟此时需要输出合并后的联盟包含了多少颗星球如果两个星球本来就在同一个联盟里那么再怎么建航道都不会改变联盟的边界此时输出当前这个联盟的大小。注意这里有一个非常容易忽略的约束每个提案一旦通过航道就真的建成了后续的提案是在这个基础上继续处理的。也就是说联盟会随着P次提案越来越“大”但永远不会拆散。理解了这一点整个问题就从“每次独立做一次连通性查询”变成了“动态维护若干个连通块并随时查询合并后的总大小”。1.2 数据范围决定了解法上限原题没有在这个标题里直接给出N、M、P的上限但按NOIP以及八校联考的惯例这类题的数据范围通常在10^5到10^6级别。这就意味着任何O(NP)或O(P²)的算法都会被卡死。比如每次提案来的时候重新用BFS或DFS遍历一遍所有星球统计一下连通块大小那光是读入加遍历的时间就完全扛不住。换句话说这道题表面上考的是“图论中的动态连通性”实际上考的就是并查集。因为并查集的单次操作几乎可以看成O(1)路径压缩加按大小合并之后N、M、P全是10^6也不慌。很多同学第一眼没有往并查集上想是因为题目背景里带了一堆“联盟”“航道”“提案”的设定导致注意力被转移了。做竞赛题最核心的能力之一就是快速剥离背景、看到本质。1.3 “联盟大小”到底维护什么我们再细化一下“联盟大小”这个概念。在并查集里每个集合都有一个代表元也就是根节点。我们需要额外开一个siz数组siz[x]表示以x为根的联盟内星球总数。初始时每个星球是独立的siz[i] 1。当读取M条已有的航道时每读一条就把两个端点所在的集合合并合并后新根的siz等于两个旧根的siz之和。这里有一个细节为什么合并后大小是相加而不是更复杂的计算因为每个星球最终只会属于一个联盟两个不同的联盟没有任何交集合并后自然就是集合大小的直接求和。这个思路放到生活里也很好理解两个班级合并成一个班新班级的人数就是两个班级人数加起来如果两个班级本来就有共同的学生那人数不能简单相加。放在并查集的场景里由于我们保证每次合并的根都是不同的所以“本来就有交集”的情况不会出现。2. 从暴力到并查集思维是怎么一步步转化的2.1 暴力做法为什么不行假设我们真的用最朴素的方式每来一个提案(u, v)就在当前图上加入这条边然后从u出发DFS整个连通块数一数星球数量输出答案。这样做的复杂度是多少不算图的存储开销单是一次DFS就是O(N)一共P次提案总复杂度O(NP)。当N和P都在10^5级别时这个数字是10^10连神仙优化都救不回来。其实还有更隐蔽的问题。如果你每次DFS之后不清理vis数组会造成状态污染如果清理又白白增加O(N)的开销。而且图是动态加边的用什么结构存图都要想半天。暴力做法不是不能写而是它让一个本来十分钟能写完的并查集题变成了一道超时后反复RE的折磨题。2.2 并查集为什么契合这个场景并查集这个名字容易让人误以为它只能处理“判断两个节点是否连通”实际上它还擅长维护“合并集合时产生的附加信息”。本题只需要两种操作查询u和v是否在同一个集合如果不在把两个集合合并并且能立刻知道合并后的大小。这两种操作恰好就是并查集最舒服的领域。我们只需要在合并的时候把旧的siz加起来赋给新根即可在O(1)时间内得到答案。反观用邻接表加DFS做动态连通性每次合并都要重新探索整个连通块代价太高。2.3 用“合并班级”来感受移动过程设想一下你手上有N个班级每个班级最初只有1个人每个人都是一个独立班级。老师读了M条“合并通知”比如“1班和2班合并”“2班和3班合并”于是1、2、3班变成一个25人的大班。接着来了P个“转班申请”每次申请给出两个学生他们在哪个班如果不在同一个班那么两个班直接合并你要报出新班级的人数。这个过程用代码写出来就是先循环M条初始边把并查集建起来再循环P个提案一边合并一边输出。可以说这道题其实没有任何“高深”的算法成分它只是非常纯粹地把并查集应用层考了一次。真正拉开差距的是那些对题面的理解偏差和代码细节。3. 核心细节初始边、提案边和siz更新的正确姿势3.1 先处理M条已有航道的用意题面里M条已有航道和P个提案是有明确先后顺序的。我们必须在读入P之前先把M条航道全部合并完毕。为什么不能把M条航道和P个提案混在一起处理因为题目的定义是“当前状态”下已经存在这M条航道所有提案都是在此基础上继续累加的。如果混在一起最终的连通块状态虽然没有变化但在做第1个提案时你本应该已经把M条边全部加进去了而不是只加了一部分。简单说初始状态不等于空图。很多同学漏输出或者答案偏小就是因为把M条初始边当成普通“建边操作”每建一条就输出一次。实际上M条初始边是“开局赠送”的根本不需要输出只需要预处理合并。3.2 同根时的输出到底是哪个数这是我在帮人查错时遇到最多的地方。给定提案(u, v)如果find(u)和find(v)结果相同说明两个星球已经在同一个联盟里此时新建航道不会产生任何合并动作。那么答案应该是什么有两种理解一种认为输出当前联盟大小一种认为输出0因为“没有合并”。按照题面“输出合并后联盟的星球数量”的表述即便没有合并这个联盟的数量也是稳定不变的所以应该输出当前联盟大小。这一点需要在读题时特别小心因为有些类似题目问的是“新合并的星球数”那种情况就是0。本题的“alliance”强调的是联盟整体所以答案不是0。3.3 合并时siz更新必须先读后写写出下面这段代码时很多人会踩一个低级坑if (fx ! fy) { fa[fx] fy; siz[fy] siz[fx]; // 正确 }但如果写反了if (fx ! fy) { siz[fy] siz[fx]; fa[fx] fy; }这里顺序其实问题不大因为siz[fx]在fa[fx]修改之前已经被读取。真正危险的是另一种写法siz[fy] siz[fx]; fa[fx] fy;如果我把这两行反过来写也就是先修改fa[fx]再读取siz[fx]那么当fx和fy碰巧是同一个变量的别名时比如find返回时被路径压缩后再看siz[fx]可能已经被覆盖。所以稳妥的方法是先取两个根和两个size再统一更新。推荐写成int fx find(u); int fy find(v); if (fx fy) { printf(%d\n, sz[fx]); } else { int newSize sz[fx] sz[fy]; fa[fx] fy; sz[fy] newSize; printf(%d\n, newSize); }这里把newSize单独算出来一方面是为了输出另一方面也是为了避免覆盖旧值。3.4 路径压缩与按数量合并的配合路径压缩是并查集优化查询速度的关键它会让树更扁。按数量合并也叫按大小合并则是让树更矮。两者一起使用时树的高度几乎是常数级别接近O(log N)再带上路径压缩可以视为近似O(1)。我在实现时习惯把并查集结构写成两个全局数组find用递归或迭代都行。递归写法代码短但在数据量极大时编译器开启O2后问题不大不放心就写非递归版本。考虑到很多学校OJ不开O2我建议用非递归或加inline的递归实现避免爆栈。后面代码会给出非递归版本的参考。4. 完整代码实现与逐段注释4.1 C写法适合直接当模板用因为题目名字里标注了Standard IO所以用标准输入输出即可。但如果P特别大建议用快读或scanf不要用cin/cout直接裸奔。这里给出一份能直接提交的结构包含注释方便大家对照。#include cstdio const int MAXN 1000005; int fa[MAXN]; int siz[MAXN]; int find(int x) { // 非递归路径压缩 int root x; while (root ! fa[root]) { root fa[root]; } while (x ! root) { int next fa[x]; fa[x] root; x next; } return root; } int main() { int n, m, p; scanf(%d%d%d, n, m, p); for (int i 1; i n; i) { fa[i] i; siz[i] 1; } // 处理已有航道 for (int i 0; i m; i) { int u, v; scanf(%d%d, u, v); int fu find(u); int fv find(v); if (fu ! fv) { // 按大小合并尽量把小集合接在大集合下面 if (siz[fu] siz[fv]) { fa[fv] fu; siz[fu] siz[fv]; } else { fa[fu] fv; siz[fv] siz[fu]; } } } // 处理提案 for (int i 0; i p; i) { int u, v; scanf(%d%d, u, v); int fu find(u); int fv find(v); if (fu fv) { printf(%d\n, siz[fu]); } else { int newsiz siz[fu] siz[fv]; if (siz[fu] siz[fv]) { fa[fv] fu; siz[fu] newsiz; } else { fa[fu] fv; siz[fv] newsiz; } printf(%d\n, newsiz); } } return 0; }4.2 代码里的几个决定性选择选择按大小合并而不是直接把fx接在fy下面原因很朴素一棵1万人的大树如果每次都把大树根接到小树根上树的高度会快速膨胀find变慢。反过来把小树接在大树下树的高度增长非常缓慢。虽然路径压缩已经能把树压扁但按大小合并可以让树的“形状”更健康两者搭配最稳。选择非递归find是因为递归在极端数据下可能爆栈。虽然这条题的N不一定能大到爆栈但养成习惯没有坏处。第二段while循环的作用是路径压缩把路径上所有节点直接挂到根上下次查找更快。另外要注意两个集合合并时我们记录的siz只对根有意义。如果某个节点不是根了它的siz保留的是历史值没有任何参考价值。所以不要试图在非根节点上读取siz那只会让你调试到怀疑人生。4.3 手造一组样例跑一遍假设N5M1P3。初始有一条航道(1,2)所以初始联盟是{1,2}大小为2其他{3},{4},{5}各为1。接下来三个提案(1,3)1和3不在同一个联盟合并后{1,2,3}输出3。(2,3)2和3已经都在同一个联盟{1,2,3}里输出3。(4,5)4和5不在同一个联盟合并后{4,5}输出2。最后答案依次是3、3、2。这个样例非常小但足以测出两类核心情况一类是合并一类是冗余边。如果你把同根的答案输出成0样例就会立刻报警。5. 常见的提交失败原因与排查清单5.1 我在调试时复盘出的几个典型错误第一个经典错误是数组开小。N最大可能到10^6如果只开了10^5读入数据直接越界。尤其是当你用了MAXN 100005而数据充满到10^6时程序可能在某次随机WA也可能RE光查这个就够你花半小时。第二个经典错误是scanf格式不对。题目是Standard IO但数据之间可能有空格换行的各种组合用scanf(%d%d)是最稳的不用关心空白符号。有人喜欢读一行用sscanf反而容易把行末换行符处理错。第三个经典错误是输出没有加换行。P次提案每一行输出一个数如果漏了\n结果会连成一串在OJ上必然判WA。这种错误在本地样例上一般看不出来因为样例输出往往只有一行一旦有多行数据就原形毕露。5.2 不同错误现象的速查表错误表现可能原因对策样例能过交上去WA一大片同根时输出0或输出错误集合大小检查提案处理逻辑确认输出当前联盟大小答案整体偏大把初始M条边也当成提案输出了分阶段处理先合并M条边再遍历P个提案答案整体偏小初始边没有全部合并就进入提案阶段确保先读完M条边并合并完大数据集TLE没关同步、用cin/cout、没加路径压缩用scanf开快读确保find有路径压缩运行报RE数组越界fa/siz只开了N级别但MP超过N数组开到上限或者动态扩容输出数字为负数或超大siz加法顺序错误把旧值覆盖了用newSize单独暂存两个siz之和5.3 最隐蔽的“数据坑”星球编号可能乱序有些人在处理M条初始边时假设端点一定满足uv于是只做单向合并。这是非常危险的。题目从来没有保证输入有序如果你只把v接到u上或者只把u接到v上后续find时方向不一致就会导致应该连通的点没有连通。正确做法是无论输入顺序如何先取两个find结果再判断是否合并。同样提案边也一样不要因为上一次合并把某个点变成了根就默认下次它还是根。每次都要重新find。6. 扩展思考如果题目不只是“加边”还能怎么做6.1 当操作变成删除边时并查集就不够用了这道题只有加边没有删边所以并查集是完美的。但如果比赛里的进阶版本要求每次操作可能是“加一条边”或“删一条边”那就不能照搬模板了。正向加边可以让集合不断合并删边却可能让集合分裂而并查集不支持分裂。这时候常见的思路是“离线倒序”把操作序列读下来先假设所有加边都完成得到最终状态然后从最后一步倒着执行操作。原本的“删除边”倒过来就是“添加边”问题又变回纯合并了。如果题目还要求可回溯则可以用可撤销并查集在合并时把操作压栈回退时逆序弹出。6.2 如果要求的不是大小而是联盟编号或最值有的“联盟”类题目问的不是联盟中星球的数量而是联盟的编号最小值、最大值或者某种统计值。做法完全一样把siz数组换成要维护的值就行。每到合并时按照你定义的规则更新一次。比如维护最小值就取min维护最大值就取max。这类变式的核心仍然是“在并查集合并时附带维护信息”。6.3 一个值得练的进阶变式如果你想检验自己对并查集动态维护的掌握程度可以试着做这样一道“仿写题”有N个点初始互相独立。会给出一串操作操作一是把u和v合并并输出新集合大小操作二是询问u所在集合大小。如果操作二是查询你不需要做任何修改代码逻辑只是把输出部分单独抽出来。看起来简单但真的写起来你会发现“查询根后再查size”和“直接用u当根去查size”是两回事前者正确后者错。这也是本题非常容易忽略的思维盲区。7. 写在最后的一点复盘这道题真正想训练我们的其实是两个习惯。第一个习惯是看到动态合并、动态查询连通性立刻反应到并查集第二个习惯是在输出答案前反复确认“这次合并到底发不发生如果发生答案是什么”。我在写第一版代码时就是把同根情况的输出忘了结果样例中只要出现一个冗余提案答案就错一位。那次的教训特别深因为问题不出在算法上而是出在“我以为的题意”上。所以建议所有准备联赛的同学做这类带背景故事的题目时先把题面里关于输出的句子圈出来再用自己的话复述一遍。如果复述出来的结果和原题一致再开始写代码。这个方法听起来很笨但真的能救你很多分。联考赛场上时间紧张与其写个暴力再慢慢改不如多花三分钟把题面读透直接把正确的并查集模板交上去。