E. Graph Composition - 题解
比赛与标签
比赛: Codeforces Round 998 (Div. 3) 标签: dfs and similar, dsu, graphs, greedy 难度: *1500
题目大意喵~
主人 sama，下午好呀！这道题是这样的呐：
我们有两个都包含 n 个顶点的图，分别叫做 F 和 G。图 F 有 m1 条边，图 G 有 m2 条边。我们可以对图 F 进行两种操作，次数不限：
- 删除边：在
F中选择一条存在的边(u, v)，然后把它删掉。 - 添加边：在
F中选择两个没有边直接相连的顶点u和v，然后给它们加上一条边。
我们的目标是，通过最少的操作次数，让图 F 和图 G 的 连通性 完全一样。也就是说，对于任意两个顶点 u 和 v，如果它们在 F 中是连通的（存在路径），那么它们在 G 中也必须是连通的；反之亦然。
我们要做的就是计算出这个最少的操作次数是多少，喵~
解题思路分析喵~
这道题的目标是让两个图的“连通性”一致。这个词听起来有点抽象，但其实它有一个非常具体的含义哦！两个顶点连通，就是说它们在同一个 连通分量 里。所以，题目的目标可以翻译成：通过最少的操作，让图 F 的连通分量划分和图 G 的连通分量划分完全相同。
既然是连通分量的问题，那本喵的 DNA 动了！并查集 (DSU) 就是解决这类问题的神器呀！
我们可以把整个问题拆解成两个独立的部分来考虑：
1. "错误"的边必须删除！(计算删除代价)
首先，我们来看看 G 的连通分量是什么样的。我们可以用并查集 dsu_g 跑一遍 G 的所有边，就能得到 G 的所有连通分量了。
现在，考虑 F 中的任意一条边 (u, v)。
- 如果
u和v在G中本来就在同一个连通分量里，那么这条边在F中是“可能有用”的，因为它维持了G中本应有的连通性。 - 但如果
u和v在G中属于 不同 的连通分量，那么F中的这条边(u, v)就是一条“错误”的边！它把两个在G中本不应该连通的集合给连起来了。为了让F的连通分量和G一致，这条边 必须被删除！
所以，第一步的删除代价就是 F 中所有连接了不同 G-连通分量的边的数量。我们把这些必须删除的边去掉，剩下的就是“合法”的边了，我们称之为 valid_f_edges。
2. "缺失"的连接需要补上！(计算添加代价)
经过第一步，我们已经把所有“错误”的边都删掉了。现在 F 中只剩下 valid_f_edges。这些边连接的顶点，在 G 中都属于同一个连通分量。
但是，这样就够了吗？不一定哦！
考虑 G 中的一个连通分量 C_g。C_g 里的所有顶点都应该在最终的 F 图里也互相连通。但是，valid_f_edges 可能不足以将 C_g 里的所有顶点都连接起来。它们可能把 C_g 划分成了好几个更小的连通块。
举个例子喵：G 中 {1, 2, 3, 4} 是一个连通分量。而 valid_f_edges 中只有一条边 (1, 2)。那么在当前的 F 中，{1, 2} 是一个连通块，{3} 是一个连通块，{4} 是一个连通块。C_g 被分成了 3 个小块。
要把 k 个独立的连通块合并成一个大的连通块，最少需要添加 k-1 条边，把它们像串糖葫芦一样串起来~
所以，第二步的添加代价就是：对于 G 的每一个连通分量，我们计算它被 valid_f_edges 划分成了多少个小连通块（假设是 k 个），然后需要添加 k-1 条边。把所有 G-连通分量的添加代价加起来，就是总的添加代价。
怎么计算这个 k 呢？我们可以再用一个并查集 dsu_f_valid！
- 用
valid_f_edges来构建dsu_f_valid。 - 遍历所有顶点
1到n。对于每个顶点i，我们知道它属于哪个G-连通分量（通过dsu_g.find(i)）和哪个由valid_f_edges形成的F-连通块（通过dsu_f_valid.find(i)）。 - 我们可以用一个
map<int, set<int>>来记录。map的键是G-连通分量的代表元，值是一个set，存放这个G-连通分量内包含了哪些F-连通块的代表元。 - 最后，遍历这个
map，对于每个G-连通分量，它对应的set的大小k就是它被分成的块数，我们就需要k-1次添加操作。
总结一下思路：
- 用并查集
dsu_g确定G的连通分量。 - 遍历
F的边，如果一条边连接了两个不同的G-连通分量，则计入删除代价。保留下“合法”的边valid_f_edges。 - 用另一个并查集
dsu_f_valid处理valid_f_edges，得到由它们构成的连通块。 - 统计每个
G-连通分量内，包含了多少个dsu_f_valid形成的连通块。如果包含k个，则需要k-1次添加操作。累加得到总的添加代价。 - 最终答案 = 删除代价 + 添加代价。
这两个过程是独立的，所以分开计算再相加，得到的就是最少操作次数，完美~
代码实现喵~
#include <iostream>
#include <vector>
#include <numeric>
#include <set>
#include <map>
#include <algorithm>
// 一个非常标准的并查集 (DSU) 结构，用来处理连通分量问题，喵~
struct DSU {
std::vector<int> parent;
std::vector<int> sz; // 用来做按大小合并的优化，效率更高！
DSU(int n) {
parent.resize(n + 1);
std::iota(parent.begin(), parent.end(), 0); // 初始化，每个节点的父亲都是自己
sz.assign(n + 1, 1); // 每个集合初始大小为 1
}
// 查找一个元素的根节点（代表元），带路径压缩优化
int find(int i) {
if (parent[i] == i)
return i;
return parent[i] = find(parent[i]);
}
// 合并两个元素所在的集合
void unite(int i, int j) {
int root_i = find(i);
int root_j = find(j);
if (root_i != root_j) {
// 按大小合并，小树合并到大树上
if (sz[root_i] < sz[root_j])
std::swap(root_i, root_j);
parent[root_j] = root_i;
sz[root_i] += sz[root_j];
}
}
};
void solve() {
int n;
long long m1, m2;
std::cin >> n >> m1 >> m2;
std::vector<std::pair<int, int>> edges_f(m1);
for (int i = 0; i < m1; ++i) {
std::cin >> edges_f[i].first >> edges_f[i].second;
}
std::vector<std::pair<int, int>> edges_g(m2);
for (int i = 0; i < m2; ++i) {
std::cin >> edges_g[i].first >> edges_g[i].second;
}
// 步骤 1: 使用 DSU 找到图 G 的所有连通分量
DSU dsu_g(n);
for (const auto& edge : edges_g) {
dsu_g.unite(edge.first, edge.second);
}
// 步骤 2: 识别 F 中“合法”的边，并计算删除代价
// “合法”的边是指连接的两个顶点在 G 中也属于同一个连通分量
std::vector<std::pair<int, int>> valid_f_edges;
valid_f_edges.reserve(m1); // 预分配内存，小优化~
for (const auto& edge : edges_f) {
if (dsu_g.find(edge.first) == dsu_g.find(edge.second)) {
valid_f_edges.push_back(edge);
}
}
// 删除代价 = F 的总边数 - 合法边数
long long removal_cost = m1 - valid_f_edges.size();
// 步骤 3: 使用另一个 DSU 处理这些“合法”的 F 边，找到它们构成的连通块
DSU dsu_f_valid(n);
for (const auto& edge : valid_f_edges) {
dsu_f_valid.unite(edge.first, edge.second);
}
// 步骤 4: 计算添加代价
// 对于 G 的每个连通分量，看它被合法的 F 边分成了多少个小块
std::map<int, std::set<int>> g_comp_to_f_valid_comps;
for (int i = 1; i <= n; ++i) {
// G 中 i 所在的连通分量的代表元
int g_root = dsu_g.find(i);
// 合法 F 边构成的图中 i 所在的连通块的代表元
int f_valid_root = dsu_f_valid.find(i);
// 记录下来：这个 G-分量 包含了那个 F-块
g_comp_to_f_valid_comps[g_root].insert(f_valid_root);
}
long long addition_cost = 0;
// 遍历所有 G-连通分量
for (const auto& pair : g_comp_to_f_valid_comps) {
// pair.second.size() 就是这个 G-分量被分成的块数 k
// 需要 k-1 条边来把它们连起来
addition_cost += pair.second.size() - 1;
}
// 步骤 5: 总代价 = 删除代价 + 添加代价
std::cout << removal_cost + addition_cost << "\n";
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}复杂度分析的说
- 时间复杂度: O((n + m1 + m2) * α(n)) 的说。
- 这里的 α(n) 是阿克曼函数的反函数，它增长得非常非常慢，对于我们遇到的所有实际情况，都可以把它看作一个很小的常数（比如小于5）。
- 构建
dsu_g需要遍历m2条边，每次unite操作的平摊时间是O(α(n))。总共是O(m2 * α(n))。 - 遍历
m1条F的边来计算删除代价和筛选合法边，需要O(m1 * α(n))。 - 构建
dsu_f_valid需要遍历valid_f_edges（最多m1条），需要O(m1 * α(n))。 - 统计添加代价时，需要遍历
n个顶点和map，map的大小最多是n。总共是O(n * α(n) + n log n)（因为set的插入），但由于代表元数量有限，这里可以更精细地分析，不过大致上是线性的。总体来看，整个算法的瓶颈在于处理边和点，所以是线性的。
- 空间复杂度: O(n + m1 + m2) 的说。
- 两个并查集都需要
O(n)的空间。 - 存储
F和G的边列表需要O(m1 + m2)的空间。 map和set最多存储n个元素，所以也是O(n)的空间。- 所以总空间是线性的。
- 两个并查集都需要
知识点与总结喵！
这道题真是一道非常经典的并查集应用题呢，把一个看似复杂的问题分解得明明白白！
核心思想 - 问题分解: 最重要的技巧就是把“让连通性一致”这个目标分解为两个独立的子问题：删除所有不该存在的连接 和 补全所有应该存在的连接。这种化繁为简的能力在算法竞赛中超级重要！
并查集的双重应用: 我们用了两次并查集，但目的不同！
- 第一次 (
dsu_g) 是为了建立一个“标准答案”，即G的连通性是怎样的。 - 第二次 (
dsu_f_valid) 是为了分析在遵守“标准答案”的前提下，我们手头已有的资源（合法的F边）能做到什么程度。
- 第一次 (
图论基础: 理解“连通分量”的本质，以及“用
k-1条边连接k个连通块”这个最基本的图论性质是解题的关键。编程技巧: 使用
std::map<Key, std::set<Value>>来统计分组信息是一个非常实用的技巧，可以清晰地处理“一个大集合里有多少个不同的小集合”这类问题。
希望本喵的讲解对主人 sama 有帮助哦！遇到图论问题不要怕，先想想它最核心的概念是什么，很多时候问题就会迎刃而解啦！加油喵~！