Operating on a Graph - 题解

标签与难度

标签: 并查集, 图论, 摊还分析, 数据结构, 链表, 启发式合并难度: 2000

题目大意喵~

主人你好呀，喵~ 来看这道有趣的图论题吧！

我们拿到一个有 $n$ 个点和 $m$ 条边的图。一开始，每个点 i 都自己形成一个独立的“小组”，也就是第 i 组。

接下来，我们要执行 $q$ 次操作。每次操作会给我们一个组号 $o_i$ 。操作规则是这样的：

首先，我们要找到所有和 $o_i$ 组 有边相连 的其他小组。如果小组 A 的一个点和小组 B 的一个点之间有边，那 A 和 B 就是相连的。
然后，所有这些被找到的小组，它们里面的所有点，都要“搬家”到 $o_i$ 组里来。也就是说，它们都会被 $o_i$ 组合并掉。
有一个特殊情况：如果 $o_i$ 组本身已经不存在了（比如它自己之前就被别的组给合并了），那这次操作就什么也不做，喵~

所有 $q$ 次操作都执行完之后，我们需要回答，每个点（从 0 到 n-1）最终属于哪个小组呢？

解题思路分析

这道题的核心是处理“小组”的合并和归属问题，一看到这个，我的DNA就动了，这不就是 并查集（Disjoint Set Union, DSU） 的经典应用场景嘛，的说！

我们可以用并查集来维护每个点属于哪个小组。find(i) 操作可以告诉我们点 i 所在小组的“代表”是谁。unite(u, v) 操作可以把 u 和 v 所在的小组合并成一个。

暴力想法的陷阱

最直接的想法是：对于每次操作 $o_i$ ，我们遍历 $o_i$ 组里的每一个点 u，再遍历 u 的所有邻居 v。如果 v 所在的组和 o_i 组不是同一个组，就把 v 的组合并到 o_i 组里。

但是，这种方法有个大大的陷阱，喵！如果一个小组变得非常非常大，比如包含了几乎所有的点，那么每次对它进行操作，我们都要遍历它内部所有的点和边，这会导致时间复杂度爆炸，肯定会超时的说！

优化的关键：维护“小组边界”

我们得换个思路。一个小组向外扩张，其实只和它“边界”上的边有关。我们不需要关心小组内部的连接情况，只需要知道这个小组和哪些“外面”的点相连。

所以，我们可以为每个小组（由它的代表点来标识）维护一个 邻接表。group_adj[root] 就存储了所有与 root 小组直接相连的外部点的列表。

当我们要对小组 $o_i$ (假设它还是一个代表点) 进行操作时：

我们遍历 group_adj[o_i] 列表。
对于列表里的每个邻居点 v，我们找到它所在小组的代表 root_v = find(v)。
根据题目要求，所有与 $o_i$ 组相连的小组都要被合并。所以，只要 root_v 不是 $o_i$ 自己，我们就需要把 root_v 组合并到 $o_i$ 组里。

合并的艺术：高效的邻接表合并

合并小组 root_v 到 $o_i$ 时，除了用并查集更新 parent[root_v] = o_i，我们还必须更新它们的邻接表。新的 $o_i$ 组的邻居，应该是原来 $o_i$ 组的邻居和所有被合并进来的小组（比如 root_v 组）的邻居的并集。

这里就体现出这道题的精髓了！

思考一个关键点：当操作 $o_i$ 时，我们遍历了 group_adj[o_i] 里的所有邻居。对于其中任何一个邻居 v，它所在的组 find(v) 都会被合并到 $o_i$ 中。这意味着，连接 $o_i$ 组和 find(v) 组的这条边，在合并后就变成了 $o_i$ 组的“内部边”。它不再是边界了！

这给了我们一个绝妙的启示：在一次操作中，原来 group_adj[o_i] 中列出的所有邻居所代表的连接，在操作后要么因为小组被合并而变为内部连接，要么邻居本身就在 $o_i$ 组内。所以，旧的 group_adj[o_i] 列表在操作后就没用了！

新的 group_adj[o_i] 应该由所有被合并进来的小组的邻接表“拼接”而成。

数据结构的选择：

如果用 std::vector 来存邻接表，合并两个 vector 需要把一个的所有元素复制到另一个，成本很高。虽然可以用启发式合并（每次都把小的合并到大的里面）来优化，总复杂度能做到 $O(M \log M)$ ，但有更优的选择！
std::list！C++ 的 std::list 是双向链表，它有一个神奇的 splice 操作，可以在 $O(1)$ 的时间内把一个链表的所有元素“剪切”并“粘贴”到另一个链表里！这简直是为我们量身定做的，喵~

最终的完美计划

初始化：
- 建立一个并查集，parent[i] = i。
- 为每个点 i 创建一个 std::list<int> group_adj[i]，存下它在原图中的所有邻居。
处理操作 op_center：
- 检查 op_center 是否还是一个小组的代表，即 find(op_center) == op_center。如果不是，说明它已经被合并了，直接跳过。
- 为了安全地遍历和修改，我们把 group_adj[op_center] 的内容用 swap 移到一个临时链表 neighbors_to_process 中。这个操作是 $O(1)$ 的。现在 group_adj[op_center] 空了。
- 遍历 neighbors_to_process，找出所有需要被合并的小组的代表点，并将它们（去重后）存起来。
- 对于每一个要被合并的代表点 root_to_merge：
  - 用并查集把它合并到 op_center：parent[root_to_merge] = op_center。
  - 用 splice 操作，把 group_adj[root_to_merge] 的全部内容瞬间移动到 group_adj[op_center] 的末尾。
- neighbors_to_process 这个临时链表里的连接关系在本次操作后都变成了内部连接，所以可以直接丢弃。
输出：所有操作结束后，对每个点 i，输出 find(i) 即可。

这个方法通过 std::list 的 splice 操作，将合并邻接表的成本降到了最低，实现了非常高效的摊还复杂度，优雅地解决了问题，喵~

代码实现

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <list>
#include <algorithm>

// DSU (并查集) 的 find 操作，带有路径压缩优化
int find_set(std::vector<int>& parent, int v) {
    if (v == parent[v]) {
        return v;
    }
    return parent[v] = find_set(parent, parent[v]);
}

// DSU 的 unite 操作，这里我们直接在主逻辑中合并，所以不需要一个单独的unite函数
// void unite_sets(std::vector<int>& parent, int a, int b) { ... }

void solve() {
    int n, m;
    std::cin >> n >> m;

    // parent[i] 存储节点i的父节点，用于并查集
    std::vector<int> parent(n);
    // iota(begin, end, value) 能用递增的值填充范围，这里是 0, 1, 2, ...
    std::iota(parent.begin(), parent.end(), 0);

    // group_adj[i] 存储代表节点为i的组的邻接表
    // 使用 std::list 是为了O(1)的splice操作，喵~
    std::vector<std::list<int>> group_adj(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        group_adj[u].push_back(v);
        group_adj[v].push_back(u);
    }

    int q;
    std::cin >> q;

    // 用来存储待合并的组的代表，避免重复合并
    std::vector<int> roots_to_merge;

    while (q--) {
        int op_center;
        std::cin >> op_center;

        // 核心检查：如果 op_center 已经不是一个组的代表，
        // 说明这个组已经被合并了，按题意什么都不做。
        if (parent[op_center] != op_center) {
            continue;
        }

        // 为了安全地遍历和修改，我们将当前组的邻接表移出。
        // swap 是 O(1) 的，非常高效！
        std::list<int> neighbors_to_process;
        neighbors_to_process.swap(group_adj[op_center]);

        // 清空上次操作留下的待合并列表
        roots_to_merge.clear();

        // 1. 收集所有需要合并的邻居组的代表
        for (int neighbor_node : neighbors_to_process) {
            int neighbor_root = find_set(parent, neighbor_node);
            // 如果邻居组不是自己，就把它加入待合并列表
            if (neighbor_root != op_center) {
                roots_to_merge.push_back(neighbor_root);
            }
        }
        
        // 2. 去重，因为多个邻居可能属于同一个组
        std::sort(roots_to_merge.begin(), roots_to_merge.end());
        roots_to_merge.erase(std::unique(roots_to_merge.begin(), roots_to_merge.end()), roots_to_merge.end());

        // 3. 执行合并
        for (int root : roots_to_merge) {
            // 在 DSU 中合并
            parent[root] = op_center;
            // 使用 O(1) 的 splice 操作合并邻接表
            // 将 root 组的邻接表内容全部移到 op_center 组的邻接表尾部
            group_adj[op_center].splice(group_adj[op_center].end(), group_adj[root]);
        }
    }

    // 输出最终结果
    for (int i = 0; i < n; ++i) {
        std::cout << find_set(parent, i) << (i == n - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    // 加速 C++ IO，让我跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(T \cdot (N+M+Q) \cdot \alpha(N))$ ，其中 $T$ 是测试用例数量。对于每个测试用例，初始化并查集和邻接表需要 $O(N+M)$ 。在 $Q$ 次查询中，我们来分析总的消耗。并查集的 find 操作带有路径压缩，其单次操作的摊还时间复杂度是 $\alpha(N)$ （一个增长极其缓慢的函数，近似于常数）。核心在于邻接表的处理。每个邻接点最多只会被遍历一次。当一个小组 op_center 执行操作后，它的邻接表 group_adj[op_center] 被清空，然后由被合并进来的小组的邻接表拼接而成。这个拼接操作 splice 是 $O(1)$ 的。一个小组一旦被合并，它就再也不会成为操作中心了。因此，图中的每条边所对应的两个邻接点，在所有操作中，只会被遍历有限次。总的时间复杂度可以摊还为 $O((N+M+Q) \cdot \alpha(N))$ ，这对于本题的数据范围来说是足够快的，呐。
空间复杂度: $O(N+M)$ 我们需要 $O(N)$ 的空间来存储并查集的 parent 数组。同时，我们需要存储所有边的信息，这些信息分布在各个 group_adj 链表中，总元素数量是 $2M$ 。所以总的空间复杂度是 $O(N+M)$ 。

知识点总结

我来总结一下这道题的精华吧！

并查集 (DSU): 解决动态连通性和集合合并问题的利器。路径压缩和按秩（或按大小）合并是其性能的关键。
摊还分析: 对于一系列操作，不是看最坏的单次操作，而是看所有操作的平均开销。本题中，虽然单次操作可能遍历很长的邻接表，但每个邻接点被遍历的次数是有限的，总成本被平摊了。
数据结构选择: 针对特定操作选择最优数据结构是算法设计的核心。这里 std::list 的 $O(1)$ splice 操作完胜了 std::vector 的 $O(N)$ 合并，是解题的关键。
问题转化: 将“合并小组”这一模糊概念，精确地转化为“合并并查集代表”和“合并小组邻接表”这两个具体操作，是解题的第一步。

希望这篇题解能帮到你，喵~ 如果还有不懂的，随时可以再来问我哦！

Operating on a Graph - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

暴力想法的陷阱 ​

优化的关键：维护“小组边界” ​

合并的艺术：高效的邻接表合并 ​

最终的完美计划 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​