看到「K-th Largest Connected Components」这个标题大多数人的第一反应是连通分量那还不简单DFS染色、Flood Fill、并查集随便拉一个出来都能搞定。但真跟着这个思路写下去你会发现自己面对的是动态加边、频繁查询的场景——每加一条边连通分量的归属和大小都在变如果每次查询都重新扫一遍全图数据范围稍大一点就直接 TLE。这道题表面上考的是连通分量实际上考的是「动态连通性」和「Top-K 查询」的组合这才是它真正有价值的地方。这篇文章不打算只贴一份 AC 代码而是把这类题的完整分析链路捋一遍题目到底在问什么、为什么常规做法会挂、并查集和有序集合怎么配合、合并时有哪些坑、复杂度怎么算、以及从这题能延伸出哪些常见变体。如果你正在刷图论和数据结构过渡段的题目或者准备各种算法竞赛这篇文章应该能帮你省下不少试错时间。1. 题目真正考的不是连通分量的求法而是动态场景下的 Top-K 查询1.1 静态做法为什么会超时先把这个题的常规版本说清楚一开始有 N 个孤立的顶点编号 1 到 N然后来 Q 次操作。操作分两种一种是加一条无向边另一种是查询当前所有连通分量里顶点数第 K 多的那个分量大小是多少。如果没有「动态」这两个字解法确实很直接读入所有边跑一遍 DFS/BFS 给每个顶点标记所属连通分量统计每个分量的顶点个数排序然后按查询输出。但问题是加边操作是穿插在查询之间的每次加边都可能改变某些分量的归属和大小。如果没有别的优化手段只能每次查询前重新跑一遍 DFS单次 O(N M)Q 次操作一加起来N 和 M 都是 2e5 量级的时候运算量直接飙到 1e10 以上。很多人最开始就是这么写的理由也很简单求连通分量我从小到大就是这么学的。但这个思路在动态场景下犯了方向性错误——DFS 求连通分量适合「静态图求一次用很多次」而这里图的形态在不停变化查询紧跟其后你必须实时维护「哪些点连通」和「每个连通分量有多大」这些信息而不是每次从头算。1.2 并查集解决连通性剩下的难点是谁来维护顺序如果对这类题有点经验会立刻想到并查集DSU。并查集天生就是处理动态连通的加边对应 union 操作判断两点是否连通对应 find 操作路径压缩和按大小合并还能让单次操作接近常数级复杂度。但并查集有一个「短板」——它只告诉你两个点是不是在一个集合里以及集合的根是谁它不能直接告诉你「现在所有连通分量里从大到小排第 K 个是多大」。所以这道题真正的核心矛盾浮出水面了你需要的是一种能在合并发生之后依然保持「所有连通分量按大小有序排列」的数据结构。这跟平衡树、有序集合这类结构天然契合。1.3 注意 K 的取值范围它是整道题的题眼这类题在设置约束时通常会给你一个很刁钻的 K常见的是 K ≤ 10或者 K ≤ 20。这个条件不是随便给的它意味着查询的时候不需要真的把全量排序只需要维护前 K 大的信息就够了。这给解法留下了巨大的优化空间也让题目从「每次排序 O(N log N)」跳到了「常数极小的维护」上。如果说并查集是这套解法的心脏那么 K 的约束就是主动脉——理解了这两个整道题的基本面貌就出来了。2. 双数据结构接力并查集管归属有序集合管顺序2.1 为什么我选 setpairint,int 而不是 multiset很多第一次写这道题的人会顺手用multisetint来存每个连通分量的大小查询的时候从尾部数 K 个。这个直觉是对的但细节上会踩一个隐蔽的坑两个大小相同的连通分量在multisetint里是两条完全相同的记录删除的时候erase(val)会把所有同值的记录一次性删掉。合并两个相同大小的分量时你本来只需要删掉两条记录、插入一条新的结果一次erase把所有相同大小的都干掉了整个集合就残了。更稳妥的写法是用setpairint, intpair 的第一个元素是连通分量大小第二个元素是这个连通分量在并查集里的根节点编号。因为每个连通分量有且只有一个根所以哪怕两个分量大小完全相同它们的 pair 也不相同set不会去重删除时定向删(size, root)就能精确删掉目标分量。2.2 初始化与查询的基本框架有了这个设计代码框架就很清晰了。初始化时每个点自成一个连通分量向set里插入(1, i)表示大小为 1、根为 i 的分量。并查集的fa数组和sz数组单独维护。#include bits/stdc.h using namespace std; const int MAXN 200005; int fa[MAXN], sz[MAXN]; int find(int x) { while (fa[x] ! x) { fa[x] fa[fa[x]]; x fa[x]; } return x; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; for (int i 1; i n; i) { fa[i] i; sz[i] 1; } setpairint, int comps; // (size, root) for (int i 1; i n; i) { comps.insert({1, i}); } while (q--) { int op; cin op; if (op 1) { int u, v; cin u v; // 合并操作的详细逻辑在下一节展开 } else { int k; cin k; if ((int)comps.size() k) { cout -1 \n; } else { auto it comps.end(); while (k--) { --it; } cout it-first \n; } } } return 0; }这里find用的是迭代写法路径压缩的效果和递归写法完全一样但避免了递归深度过大带来的爆栈风险。虽然按大小合并后并查集树高是 O(log N)递归也不太容易爆但竞赛里养成写迭代 find 的习惯没有坏处。2.3 C 之外的实现选型如果是用 Java 写可以直接用TreeSetlong[]或者封装一个节点类实现Comparable接口按大小和根编号排序。Python 的话竞赛环境下没有内置的有序集合要么自己写平衡树要么换个思路因为 K 通常很小可以用一个heapq堆维护当前最大的若干个分量并配合一个delete_later的懒惰删除标记。这个思路本质上就是下面第四部分要说的「独立 Top-K 堆」这里先不展开。3. 合并两个分量的完整过程先删旧记录再插新记录3.1 合并操作的标准三段式加边操作处理的核心就是并查集的 union。完整过程可以拆成三步第一步找到两个端点的根ru find(u)、rv find(v)。如果ru rv说明它们本来就在同一个连通分量里这条边是无效边自环或重复边什么都不用做直接 continue。第二步从set里删除两条旧记录(sz[ru], ru)和(sz[rv], rv)。这一步是在所有数据结构层面删除旧分量。第三步按大小合并两个集合。保证小树并到大树上fa[rv] ru然后把sz[ru] sz[rv]。最后向set里插入新记录(sz[ru], ru)代表合并后的新分量。if (op 1) { int u, v; cin u v; int ru find(u); int rv find(v); if (ru rv) continue; comps.erase({sz[ru], ru}); comps.erase({sz[rv], rv}); if (sz[ru] sz[rv]) swap(ru, rv); fa[rv] ru; sz[ru] sz[rv]; comps.insert({sz[ru], ru}); }这段代码看起来简单但每一步都有值得推敲的地方。特别是第二部很多人会漏掉「先删除旧记录」这个动作直接insert合并后的新记录结果 set 里同时存在旧大小和新大小两条记录导致后面查询第 K 大的结果全是错的。3.2 为什么大小相同也要安心删除刚才提到用setpairint,int就是为了避免同大小分量互相覆盖。假定现在有两个大小为 2 的分量根分别是 3 和 5那么集合里存的就是{2, 3}和{2, 5}。合并后新分量大小是 4我们依次删除{2, 3}和{2, 5}再插入{4, 3}。因为{2, 3}和{2, 5}是不同的 pairerase时完全不会误删。这里还有一个极其重要的细节删除时用的sz[ru]和sz[rv]必须是当前真实大小。如果 ru 和 rv 本身就已经是别人合并后的树根那么sz数组里存的值就是合并后的大小没有过期问题。可一旦你把某个节点作为非根节点参与运算它的sz值就不可信了。所以合并之前一定先find再取根节点上的sz不能直接拿原始输入节点的sz去 set 里找。3.3 路径压缩对 set 里根节点的冲击这里回答一个常见困惑find过程中做了路径压缩会不会导致 set 里记录的那个根节点编号失效答案是不会。路径压缩只是把路径上的点的fa直接指向根根节点本身的编号没有变sz[root]也没有变。所以 set 里的(size, root)记录依然有效。真正的坑在于合并之后旧根会变成新根的子节点此时它的sz不再更新。如果后续还有一条边连接这个节点和新根find返回的是新的根set 里的记录以新根为准不会出错。这就是为什么我们始终强调并查集里sz的有效值只在根节点上所有和 set 有关的增删改查都必须在根节点上操作。3.4 平行边和自环不是特殊而是常态实际测试数据里会出现1 1 2后紧接着再来一条1 1 2的情况也可能出现1 5 5这种自环。自环的find(5) find(5)直接 continue。平行边的两端点也早已在同一个集合里同样 continue。这些判断在合并逻辑里已经天然处理了不需要额外特判但如果你写的是「先删除再判断 uv」就会出问题——第一次加边后 set 里已经删掉了旧记录、插入了新记录第二条平行边如果强行删除会发现(sz[ru], ru)可能已经不在了erase返回 0 但 C 不会报错只是默默没删掉任何东西结果 scope 就乱了。所以判断ru rv一定要放在最前面。4. 查询第 K 大的三种姿势以及它们的性能差异4.1 从 set 尾部反着数 K 步最稳也最直观查询时comps里的元素按(size, root)升序排列。最大值在集合末尾comps.rbegin()指向最大的那个。要查第 K 大把迭代器从comps.end()开始往前移动 K 步即可int k; cin k; if ((int)comps.size() k) { cout -1 \n; continue; } auto it comps.end(); while (k--) { --it; } cout it-first \n;这里必须先判断comps.size() k否则迭代器往前移动会越过begin()这是未定义行为。看似很小的细节一旦出现就极难排查因为在某些编译器和数据组合下它可能「碰巧」不崩却在另外的组合下输出乱值。复杂度上set的迭代器每次--it是平摊常数时间所以一次查询是 O(K)。K 通常不超过 20这个成本几乎可以忽略。这是我最推荐的做法因为代码逻辑任何人都能一眼看懂不容易藏 bug。4.2 维护一个独立的 top-K 堆省空间但费心另一种常见思路是单独维护一个大顶堆或小顶堆始终只保存当前最大的 K 个分量。查询时直接从堆顶往下数 K 个。听起来更高效因为堆里最多只有 K 个元素而不是 N 个但实践中它需要面对一个很麻烦的问题合并一个旧分量时如何从堆里精确删除堆是一种支持「插入」和「取最大/最小」的数据结构它不擅长按值删除任意元素。于是你得引入「懒惰删除」删除时不在堆里物理删除而是标记这个元素已经失效下次取堆顶时把标记过的失效元素弹出。配合priority_queue实现通常得用tupleint,int,int存大小、根编号、版本号每次合并时版本号加一。这套逻辑写下来代码量比 set 方案多出不少而且版本号设计稍有疏忽就容易漏标。所以我的建议是除非题目把 K 放大到 1e5 级别使得「全量存储 set」的空间成本不可接受否则不要用独立的 top-K 堆。set 全量存储 N 个 pair空间是 O(N)在 N 2e5 时约 3MB完全不是压力。4.3 有人说可以用平衡树做 split其实没必要还有一种偏「重量级」的做法用__gnu_pbds::tree或者手写 FHQ Treap按大小分裂出前 K 个。这种方案在处理「动态排名」类问题确实更通用比如查第 K 大还要同时支持修改、插入、删除等操作。但本题的查询稳定发生在 set 尾部K 又很小引入平衡树分裂完全是大炮打蚊子代码复杂度和出错风险不成比例上升。我还是那句话能用简单方案解决就不要展示复杂技巧。5. 复杂度分析、常数优化与大样例构造5.1 理论复杂度并查集近乎常数set 操作才是大头先给出一份整体的复杂度表方便对照操作并查集部分有序集合部分总复杂度加边两次 find一次 union两次 erase一次 insertO(α(N) log N)查询无从尾部移动 K 步O(K)初始化建 N 个根插入 N 条记录O(N log N)注意这里的 log N 是有序集合操作带来的。每次加边最多erase两次、insert一次也就是大约 3 次 O(log N) 操作。Q 2e5 时也就是 6e5 次 log 级别的平衡树调整运行时间通常在一秒以内。查询部分因为 K ≤ 20实际开销比加边还要小。5.2 路径压缩为什么放在 find 里而不是 union 里并查集本身有两个优化路径压缩和按大小合并。有些初学者会问为什么不直接用按大小合并就够了还要路径压缩其实两个优化解决的问题不同按大小合并是让树高保持 O(log N)路径压缩是让单次 find 的后续代价更低。两者合在一起单次 find 的摊还复杂度才能接近 α(N) 这个近乎常数的上界。在这道题里并查集操作本身不是瓶颈但保证find的高效能让整体更稳。5.3 怎么构造压力测试数据刷题时最怕「本地过了提交 WA」这种情况多是因为测试数据覆盖不到边界。针对这道题我建议你自己构造几类特殊数据全单点查询没有加边操作只有2 1所有分量大小都是 1。检查初始化是否正确。全加边把 N 个点连成一条链最后变成一个大小为 N 的分量。这个过程中每次合并都要保证 set 里删干净旧记录。加边后立刻查询同一根节点比如1 1 2后马上2 1验证合并后新记录确实已经插入且旧记录被删掉。K 超过当前分量总数比如 N1 时查询2 2必须输出 -1不能崩。大量重复边反复1 1 2和1 2 1验证ru rv分支不会破坏 set。对拍的时候可以先写一个每次查询都重算连通分量的暴力版本随机生成小规模数据跑上几万组对比输出。像这种思路清晰的题对拍基本能抓出所有隐藏问题。6. 从这题延伸出去的常见变体一次全部学会6.1 断边操作的通用解法离线倒序这题的加边操作是不断合并并查集天然支持。如果题目改成「删除一条边查询第 K 大分量」怎么办边删边并查集处理不了至少标准并查集不行。但如果你把操作全部离线读入从最终状态开始逆着处理删除操作就变成了添加操作先假设所有操作执行完毕后的最终图然后从最后一次操作往前扫。删除边变成加边并查集可以正常合并查询操作保持不变答案逆序输出即可。这是动态图问题里非常经典的「时光倒流」技巧。但要注意一点只有被实际删除过的边才需要离线处理。如果一条边从头到尾就没被删过那它应该作为初始边加入最终图。实现细节上通常用一个setpairint,int存所有边标记哪些被删除过这一步处理不好容易在边界处翻车。6.2 从第 K 大变成第 K 小改动只有一行如果查询的是第 K 小连通分量只需把第二部分的查询逻辑从comps.end()改成comps.begin()开始往后推进或者把 pair 的大小取负号存储让原来的「大」变成「小」。数据结构的核心不变变的只有方向。6.3 节点带权重之后怎么办如果每个点有非负权重要求查询权重和第 K 大的连通分量思路完全一致把sz数组的类型从 int 改成 long long初始化时sz[i] w[i]合并时sz[ru] sz[rv]set 里存的分量大小变成权重和。需要注意权重的数据范围超过 2e5 就应该开 long long否则溢出后 set 的排序基准就错了。6.4 这类题的工程价值不只存在于竞赛单纯看这道题它是个标准的竞赛题。但「动态合并 查询 Top-K」这个组合在工程里也有很多影子。比如图数据库里实时维护某个社交网络中的连通群体规模排名、在大规模分片系统中维护集群的成员数量分布、或者在建模软件里动态合并多边形区域并查询面积最大的前几个区域。核心逻辑都离不开并查集和有序结构的配合。回到这道题本身我最想强调的还是那个容易被忽略的细节合并时先删旧记录再插新记录全程使用根节点的sz值。这个小细节决定了整个解法能不能跑通。如果你在看这道题之前对并查集的理解还停留在「只是用来判断连通性」那么从现在开始可以进阶一步——并查集维护的连通分量信息可以和任何有序数据结构联动从而支持排序、Top-K、区间统计等更多查询。这才是动态连通性问题里最值得掌握的思维方式。