自动搬运

查看原文

来自洛谷，原作者为

	Perta broken tower

搬运于2025-08-24 22:54:14，当前版本为作者最后更新于2024-01-08 20:24:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

若两张图点集的交集为空，则分别 kruskal 后双指针即可。

若交集不为空，当前双指针中对应的两张图所保留的点对需要减去重复的。假设连通块有编号，设 $T_{i,j}$ 为既在第一个图中的 $i$ 号连通块，又在第二个图中的 $j$ 号连通块的点数，则重复的点对为 $\sum\frac{T_{i,j}(T_{i,j}-1)}{2}$。

那么一张图并查集合并，另一张图并查集撤销。注意这个时候需要开个 vector 存每个连通块内的点用于修改 $T_{i,j}$ 与撤销并查集，启发式合并/分裂即可。对于连通块的编号，将其当做并查集的根节点，使用 hash_table / unordered_map 更为方便。

$O(n\log n+m\log m)$

难看的 Code