> ✅ **OJ 验证通过**：Accepted（runid 4115392，2026-08-14 提交于校内 OJ Contest3056） ## 题目大意给定两个无向简单图 $F$ 和 $G$，顶点数均为 $n$。每次操作可在 $F$ 中删除一条边，或在 $F$ 中无边的一对点间添加一条边。求使 $F$ 满足"**任意 $u, v$ 在 $F$ 中连通当且仅当在 $G$ 中连通**"所需的最小操作数。$t$ 组数据，$\sum n, m_1, m_2 \le 2 \times 10^5$。 ## 思路分析 "连通当且仅当"意味着最终 $F$ 的**每个连通块与 $G$ 的对应连通块点集完全一致**。用并查集分别处理两个图，设 $G$ 的连通块数为 $c_2$，总代价分两部分： **1. 必须删除的边 $x$**：$F$ 中两端点不在 $G$ 同一连通块内的边。保留它会令 $G$ 中本不连通的点连通，必须删掉。 **2. 必须添加的边**：删掉跨块边后，$G$ 的每个连通块 $T$ 内被 $F$ 剩余边分成 $k_T$ 个连通块，需要 $k_T - 1$ 条边把它们连成一整块。设 $K = \sum_T k_T$，则需添加 $K - c_2$ 条边。 > **关键细节**：$k_T$ 必须在删除跨块边**之后**计算。实现上新建一个临时并查集 $H$，只合并 $F$ 中两端同属一个 $G$ 块的边，$H$ 的连通块即"删边后"$F$ 的连通块。于是 $K$ 等于不同的 $(find_G(u), find_H(u))$ 二元组个数（对每个点取对去重）。最终答案： $$ \text{ans} = x + K - c_2 $$ **直观理解**：被删的跨块边与新增的连接边各自独立计一次操作；$F$ 块内冗余边（非树边）保留即可，不影响连通性，无需处理。 ## 复杂度分析并查集总操作 $O((n + m_1 + m_2)\,\alpha(n))$，每组数据近乎线性，满足 $\sum n \le 2 \times 10^5$。 ## 参考代码 ```cpp #include using namespace std; typedef long long ll; struct DSU { vector p; DSU(int n) { p.resize(n + 1); iota(p.begin(), p.end(), 0); } int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); } void unite(int a, int b) { p[find(a)] = find(b); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n, m1, m2; cin >> n >> m1 >> m2; DSU F(n), G(n); vector> ef(m1); for (int i = 0; i < m1; i++) { cin >> ef[i].first >> ef[i].second; F.unite(ef[i].first, ef[i].second); } for (int i = 0; i < m2; i++) { int u, v; cin >> u >> v; G.unite(u, v); } // H: 只合并不跨 G 块的 F 边（即删除跨块边后 F 的连通块） DSU H(n); ll x = 0; for (auto &e : ef) { if (G.find(e.first) != G.find(e.second)) x++; else H.unite(e.first, e.second); } set> pairs; set gblocks; for (int i = 1; i <= n; i++) { pairs.insert({G.find(i), H.find(i)}); gblocks.insert(G.find(i)); } ll ans = x + (ll)pairs.size() - (ll)gblocks.size(); cout << ans << '\n'; } return 0; } ```