并查集动态维护连通块大小：‘星球联盟‘题解与易错点

考场上看到“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 并查集为什么契合这个场景

并查集这个名字容易让人误以为它只能处理“判断两个节点是否连通”，实际上它还擅长维护“合并集合时产生的附加信息”。本题只需要两种操作：

1. 查询u和v是否在同一个集合；
2. 如果不在，把两个集合合并，并且能立刻知道合并后的大小。

这两种操作恰好就是并查集最舒服的领域。我们只需要在合并的时候，把旧的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 手造一组样例跑一遍

假设N=5，M=1，P=3。初始有一条航道(1,2)，所以初始联盟是{1,2}大小为2，其他{3},{4},{5}各为1。

接下来三个提案：

1. (1,3)：1和3不在同一个联盟，合并后{1,2,3}，输出3。
2. (2,3)：2和3已经都在同一个联盟{1,2,3}里，输出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 不同错误现象的速查表

5.3 最隐蔽的“数据坑”：星球编号可能乱序

有些人在处理M条初始边时，假设端点一定满足u<v，于是只做单向合并。这是非常危险的。题目从来没有保证输入有序，如果你只把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. 写在最后的一点复盘

这道题真正想训练我们的，其实是两个习惯。第一个习惯是看到动态合并、动态查询连通性，立刻反应到并查集；第二个习惯是在输出答案前，反复确认“这次合并到底发不发生，如果发生，答案是什么”。我在写第一版代码时，就是把同根情况的输出忘了，结果样例中只要出现一个冗余提案，答案就错一位。那次的教训特别深，因为问题不出在算法上，而是出在“我以为的题意”上。

所以建议所有准备联赛的同学，做这类带背景故事的题目时，先把题面里关于输出的句子圈出来，再用自己的话复述一遍。如果复述出来的结果和原题一致，再开始写代码。这个方法听起来很笨，但真的能救你很多分。联考赛场上时间紧张，与其写个暴力再慢慢改，不如多花三分钟把题面读透，直接把正确的并查集模板交上去。