GTA 6 联机网络重组

算法思路

一次操作只能增加或删除一条边，代价都是 $1$。题目要求的不是让 $A$ 与 $B$ 的边集相同，而是让两者的连通块划分相同，因此只看哪些边破坏了目标划分。

在 $B$ 中跨越两个不同连通块的 $A$ 边，在最终图里不可能存在，必须全部删除。

删掉这些边以后，$A$ 的每个连通块都整体落在某个 $B$ 连通块内部。若某个 $B$ 连通块内还有 $p$ 个互不相连的 $A$ 碎片，补 $p-1$ 条边就能把它们接成一个整体。

于是先对 $B$ 建并查集，得到每个顶点在 $B$ 中的连通块，记块数为 $k_{B}$；再扫 $A$ 的每条边，两端在 $B$ 中不同块就计入答案并跳过，否则并入第二个并查集；最后统计第二个并查集的根节点个数 $P$（孤立点各算一块），输出跨块边数加上 $P-k_{B}$。

这里的 $P-k_{B}=\sum_{C}(p_{C}-1)$，其中 $p_{C}$ 是 $B$ 的连通块 $C$ 内 $A$ 的碎片个数。

正确性证明

最终图中任意两点连通当且仅当它们在 $B$ 中连通。若 $A$ 中存在边 $(u,v)$ 而 $u,v$ 在 $B$ 中不连通，这条边在最终图中必须不存在，只能删除；不同的跨块边互不相同，所以删除次数不少于跨块边数 $D$。

删掉跨块边后，设第 $i$ 个 $B$ 连通块内 $A$ 的碎片数为 $p_{i}$，有 $\sum p_{i}=P$。最终第 $i$ 个 $B$ 连通块必须连通，而一次加边最多把两个碎片合并，所以至少要 $p_{i}-1$ 次加边，合计不少于 $P-k_{B}$。

这样的下界可以取到：先删除全部 $D$ 条跨块边，此时同一 $B$ 连通块内的两个不同碎片之间没有 $A$ 的边，任取两个碎片中的顶点 $x$ 与 $y$，它们不相邻，添加 $(x,y)$ 合法；每加一次碎片数减一，加 $p_{i}-1$ 次后该块内所有 $A$ 顶点连通。对所有 $B$ 连通块重复该过程，总操作数恰为 $D+P-k_{B}$。

因此最少操作次数就是 $D+P-k_{B}$。

复杂度分析

两次并查集，时间复杂度 $O((n+m_{1}+m_{2})\alpha(n))$，统计 $P$ 与 $k_{B}$ 各需 $O(n)$。空间复杂度 $O(n+m_{1}+m_{2})$。答案在 $2\times 10^{5}$ 量级，使用 64 位整数更稳妥。