企业官网建设流程全解析

看到「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 为什么我选 set<pair<int,int>> 而不是 multiset

很多第一次写这道题的人，会顺手用multiset<int>来存每个连通分量的大小，查询的时候从尾部数 K 个。这个直觉是对的，但细节上会踩一个隐蔽的坑：两个大小相同的连通分量，在multiset<int>里是两条完全相同的记录，删除的时候erase(val)会把所有同值的记录一次性删掉。合并两个相同大小的分量时，你本来只需要删掉两条记录、插入一条新的，结果一次erase把所有相同大小的都干掉了，整个集合就残了。

更稳妥的写法是用set<pair<int, int>>，pair 的第一个元素是连通分量大小，第二个元素是这个连通分量在并查集里的根节点编号。因为每个连通分量有且只有一个根，所以哪怕两个分量大小完全相同，它们的 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; } set<pair<int, 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 写，可以直接用TreeSet<long[]>或者封装一个节点类，实现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 为什么大小相同也要安心删除

刚才提到用set<pair<int,int>>就是为了避免同大小分量互相覆盖。假定现在有两个大小为 2 的分量，根分别是 3 和 5，那么集合里存的就是{2, 3}和{2, 5}。合并后新分量大小是 4，我们依次删除{2, 3}和{2, 5}，再插入{4, 3}。因为{2, 3}和{2, 5}是不同的 pair，erase时完全不会误删。

这里还有一个极其重要的细节：删除时用的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。这些判断在合并逻辑里已经天然处理了，不需要额外特判，但如果你写的是「先删除，再判断 u==v」，就会出问题——第一次加边后 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实现，通常得用tuple<int,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 操作才是大头

先给出一份整体的复杂度表，方便对照：

注意这里的 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 超过当前分量总数：比如 N=1 时查询2 2，必须输出 -1，不能崩。
• 大量重复边：反复1 1 2和1 2 1，验证ru == rv分支不会破坏 set。

对拍的时候，可以先写一个每次查询都重算连通分量的暴力版本，随机生成小规模数据，跑上几万组对比输出。像这种思路清晰的题，对拍基本能抓出所有隐藏问题。

6. 从这题延伸出去的常见变体，一次全部学会

6.1 断边操作的通用解法：离线倒序

这题的加边操作是不断合并，并查集天然支持。如果题目改成「删除一条边，查询第 K 大分量」怎么办？边删边，并查集处理不了（至少标准并查集不行）。但如果你把操作全部离线读入，从最终状态开始逆着处理，删除操作就变成了添加操作：

先假设所有操作执行完毕后的最终图，然后从最后一次操作往前扫。删除边变成加边，并查集可以正常合并；查询操作保持不变，答案逆序输出即可。这是动态图问题里非常经典的「时光倒流」技巧。

但要注意一点：只有被实际删除过的边才需要离线处理。如果一条边从头到尾就没被删过，那它应该作为初始边加入最终图。实现细节上，通常用一个set<pair<int,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、区间统计等更多查询。这才是动态连通性问题里最值得掌握的思维方式。