NekoNowcoder

Appearance

Connect Graph - 题解 ​

标签与难度 ​

标签: 并查集 (Disjoint Set Union), 图论 (Graph Theory), 数据结构 (Data Structures), 启发式合并 (Heuristic Merge), 按大小合并 (Union by Size)

难度: 1600

题目大意喵~ ​

各位算法爱好者，大家好喵~！我是你们最爱的小我，今天我们要一起解决一个关于图连通性的有趣问题，呐！

题目是这样的：我们有一个图，一开始有 NN 个点和 m1m_1 条边。我们把这个初始状态叫做第 0 天。之后呢，我们会按顺序再添加 m2m_2 条边，每添加一条边就过去一天。也就是说，第 ii 天我们会添加第 ii 条新边 (1≤i≤m21 \le i \le m_2)。

我们的任务是，对于图中的每一个点，找出它最早是在第几天与 1 号点实现了连通。如果一开始（第 0 天）就和 1 号点连通，那么答案就是 0。如果一个点直到最后都没有和 1 号点连通，我们用 -1 表示（虽然题目数据保证所有点最终都会连通，但这是个好习惯~）。

简单来说，就是追踪每个点是什么时候 "抱上" 1 号点大腿的，喵~

解题思路分析 ​

这道题的核心是处理动态的连通性问题。一看到“连通”、“合并”、“集合”这些关键词，我的DNA就动了！这不就是并查集 (Disjoint Set Union, DSU) 的主场嘛，喵！

Step 1: 为什么是并查集？ ​

并查集是一种非常擅长维护和查询“朋友的朋友也是朋友”这种关系的数据结构。在图论里，它能高效地判断两个点是否在同一个连通块里，以及将两个连通块合并成一个。这和我们题目的需求完美契合！

  • find(x): 查找点 x 所在的连通块的“老大”（代表节点）。
  • unite(x, y): 将点 x 和点 y 所在的连通块合并。

Step 2: 如何记录“什么时候”连通？ ​

普通的并查集只能告诉我们“是否”连通，但题目问的是“什么时候”连通。一个点 u 与 1 号点连通，是在它所在的连通块与 1 号点所在的连通块合并的那一刻发生的。

所以，我们可以在每次执行 unite(u, v) 操作时，检查一下：

  1. u 和 v 是不是已经在一个连通块里了？如果是，那这次加边没有改变连通性，直接跳过。
  2. 如果不在一个连通块里，那么其中一个连通块是否已经包含了 1 号点？
    • 假设 u 所在的连通块已经和 1 号点连通，而 v 所在的连通块没有。那么在合并之后，v 所在的整个连通块里的所有点，就都在这一天和 1 号点连通啦！我们就把这些点的答案更新为当前的天数。
    • 反之亦然，如果 v 的连通块包含 1 号点，我们就更新 u 连通块里所有点的答案。

Step 3: 如何高效地找到一个连通块里的所有点？ ​

标准并查集只记录了每个节点的父节点，要找到一个连通块里的所有成员，需要从每个点出发向上找到根，效率很低。

这里就需要一个聪明的技巧了！我们可以对并查集进行一点小小的改造：用一个 std::vector 来维护每个连通块里的所有节点。我们让这个 vector 挂在连通块的代表节点（也就是“老大”）上。

比如，component_members[root] 就存储了以 root 为代表的连通块中的所有节点。

Step 4: 启发式合并！让合并更优雅~ ​

当我们合并两个连通块时，比如把 root_u 的块合并到 root_v 的块，我们需要把 component_members[root_u] 里的所有节点都移动到 component_members[root_v] 里。

如果每次都把一个大集合合并到一个小集合里，那移动操作就会非常耗时。想象一下，一只小猫加入一个大猫群，总比让整个大猫群搬家去找那只小猫要方便得多吧？喵~

这就是启发式合并 (Heuristic Merge)，也叫按大小合并 (Union by Size) 的思想：总是将节点数量较少的集合，合并到节点数量较多的集合中去。

这样做有什么好处呢？可以证明，每个节点最多被移动 log⁡N\log N 次。因为每次它被移动时，它所在的新集合的大小至少是原来集合的两倍。一个数最多翻倍 log⁡N\log N 次就会超过 NN。所以，所有合并操作的总时间复杂度大约是 O(Nlog⁡N)O(N \log N)，非常高效！

算法总结 ​

好啦，整理一下我们的完整作战计划：

  1. 初始化:

    • 创建一个并查集，每个点 i 的父节点是它自己 parent[i] = i。
    • 创建一个 vector<int> component_members[N]，component_members[i] 初始化为只包含 {i}。
    • 创建一个答案数组 connection_day[N]，全部初始化为 -1，并且 connection_day[1] = 0，因为 1 号点在第 0 天就和自己连通了嘛。

  2. 处理第 0 天的边:

    • 遍历 m1m_1 条初始边 (u, v)，调用 unite(u, v, 0) 进行合并。

  3. 处理第 1 到 m2m_2 天的边:

    • 对于第 i 天（从 1 到 m2m_2），读取新边 (u, v)，调用 unite(u, v, i)。

  4. unite(u, v, day) 函数的逻辑:

    • 找到 u 和 v 的代表节点 root_u 和 root_v。
    • 如果 root_u == root_v，说明它们已经连通，直接返回。
    • 找到 1 号点所在的连通块的代表 root_of_1 = find(1)。
    • 按大小合并：为了效率，我们把小的集合合并到大的集合里。如果 component_members[root_u] 的大小比 component_members[root_v] 小，就交换 root_u 和 root_v。这样可以保证我们总是把 root_v 合并到 root_u。
    • 更新答案：在合并前，检查 root_u 和 root_v 是否有一个是 root_of_1。
      • 因为我们已经保证了 root_u 是较大的集合，所以如果 root_u == root_of_1，那么 root_v 所在的（较小的）集合里的所有节点，都在 day 这一天和 1 号点连通了！我们遍历 component_members[root_v]，更新它们的 connection_day。
    • 执行合并：将 root_v 的父节点设为 root_u，并把 component_members[root_v] 中的所有节点都移动到 component_members[root_u] 中。

  5. 输出结果: 遍历并输出 connection_day 数组。

这样，我们就能高效又准确地解决这个问题啦！是不是很清晰呢，喵~

代码实现 ​

这是我根据上面的思路，精心重构的一份代码~ 注释超详细的哦！

cpp
#include <iostream>
#include <vector>
#include <numeric>

// 定义一个常量，表示节点数量的最大值，喵~
const int MAXN = 200005;

// parent[i] 存储节点 i 的父节点，用于并查集
int parent[MAXN];
// component_members[i] 存储以 i 为根的连通块中的所有节点
std::vector<int> component_members[MAXN];
// connection_day[i] 存储节点 i 最早与节点 1 连通的天数
int connection_day[MAXN];

// 并查集的 find 操作，带有路径压缩优化
// 找到 x 所在集合的根节点（老大）
int find_set(int x) {
    if (x == parent[x]) {
        return x;
    }
    // 路径压缩：直接将 x 的父节点指向根节点，下次查找会更快
    return parent[x] = find_set(parent[x]);
}

// 合并两个节点所在的集合，并记录连通时间
void unite_sets(int u, int v, int day) {
    // 找到 u 和 v 各自的老大
    int root_u = find_set(u);
    int root_v = find_set(v);

    // 如果老大是同一个人，说明早就在一个连通块里了，啥也不用做
    if (root_u == root_v) {
        return;
    }

    // 启发式合并（按大小合并）：总是把小的集合合并到大的集合里
    // 这样可以减少节点移动的总次数，提高效率！
    if (component_members[root_u].size() < component_members[root_v].size()) {
        std::swap(root_u, root_v);
    }
    // 经过交换，现在 root_u 对应的集合总是更大（或相等）的

    // 检查是否有一方已经和节点 1 连通
    int root_of_1 = find_set(1);

    // 如果大的集合(root_u)是包含1的那个，那么小的集合(root_v)里的所有节点
    // 都在今天(day)和1连通了！
    if (root_u == root_of_1) {
        for (int member : component_members[root_v]) {
            // 只更新那些之前还没连通的节点
            if (connection_day[member] == -1) {
                connection_day[member] = day;
            }
        }
    }
    // 注意：因为我们把小集合合并到大集合，所以如果 root_v == root_of_1，
    // 那么合并后新的根会是 root_u。1号点所在的集合的根会改变。
    // 但我们的逻辑是正确的，因为下一次 find(1) 会返回新的根 root_u。
    // 所以只需要检查一次就够了。

    // 开始合并过程
    // 1. 将小集合的根指向大集合的根
    parent[root_v] = root_u;
    // 2. 将小集合的所有成员移动到大集合的 vector 中
    component_members[root_u].insert(
        component_members[root_u].end(),
        component_members[root_v].begin(),
        component_members[root_v].end()
    );
    // 3. 清空小集合的 vector，因为它已经不存在了
    component_members[root_v].clear();
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 初始化
    for (int i = 1; i <= n; ++i) {
        parent[i] = i; // 每个节点一开始都是自己的老大
        component_members[i].push_back(i); // 每个集合一开始只有自己
        connection_day[i] = -1; // 默认都未与1连通
    }
    connection_day[1] = 0; // 节点1在第0天就和自己连通了

    int m1, m2;
    std::cin >> m1 >> m2;

    // 处理第0天的 m1 条边
    for (int i = 0; i < m1; ++i) {
        int u, v;
        std::cin >> u >> v;
        unite_sets(u, v, 0);
    }
    
    // 检查一下第0天就和1连通的所有节点
    int initial_root_of_1 = find_set(1);
    for(int member : component_members[initial_root_of_1]){
        if(connection_day[member] == -1){
            connection_day[member] = 0;
        }
    }

    // 处理后续 m2 天的边
    for (int day = 1; day <= m2; ++day) {
        int u, v;
        std::cin >> u >> v;
        unite_sets(u, v, day);
    }

    // 输出每个点的答案
    for (int i = 1; i <= n; ++i) {
        std::cout << connection_day[i] << "\n";
    }

    return 0;
}

一个小小的修正喵：在处理完第0天的所有边后，1号点所在的连通块可能已经变大了。所以需要把这个连通块里所有节点的答案都更新为0。我在代码里加了一小段逻辑来处理这个初始情况，这样更严谨~

复杂度分析 ​

  • 时间复杂度: O((m1+m2)α(N)+Nlog⁡N)O((m_1+m_2)\alpha(N) + N \log N)

    • 每次 unite_sets 操作中，find_set 的调用因为路径压缩优化，其均摊时间复杂度是 O(α(N))O(\alpha(N))，其中 α(N)\alpha(N) 是反阿克曼函数，增长极其缓慢，对于所有实际情况都可以看作是一个很小的常数（小于5）。所以 m1+m2m_1+m_2 次加边带来的并查集操作总时间是 O((m1+m2)α(N))O((m_1+m_2)\alpha(N))。
    • 关键在于启发式合并。每个元素一生中最多被从一个 vector 移动到另一个 vector O(log⁡N)O(\log N) 次。因为每次移动，它所在的新集合大小至少是旧集合的两倍。所以所有合并操作中移动元素的总次数是 O(Nlog⁡N)O(N \log N)。
    • 因此，总的时间复杂度由这两部分共同决定，主要是由启发式合并主导。

  • 空间复杂度: O(N)O(N)

    • parent 数组需要 O(N)O(N) 的空间。
    • connection_day 数组需要 O(N)O(N) 的空间。
    • component_members 是一个 vector 数组，但所有 vector 中存储的元素总数加起来就是 NN 个，所以它也只占用 O(N)O(N) 的空间。

知识点总结 ​

这道题真是一次愉快的算法之旅呢，喵~ 我们复习和运用了几个非常重要的知识点：

  1. 并查集 (DSU): 解决图连通性问题的利器，核心是 find 和 unite 操作。
  2. 路径压缩 (Path Compression): find 操作的强力优化，能极大地提升查找效率。
  3. 按大小合并 (Union by Size) / 启发式合并: unite 操作的优化，通过总是将小集合并入大集合，避免了最坏情况的发生，保证了合并操作的整体高效性。
  4. 数据结构改造: 我们没有局限于标准的并查集，而是根据题目需求（需要获取集合内所有成员），为它增加了一个 vector 来存储成员列表，体现了算法的灵活性。
  5. 动态问题处理: 学会了如何将一个静态的数据结构（并查集）应用于一个带有时间维度的动态问题中，通过在合并时机更新答案来解决问题。

希望这篇题解能帮助到你，喵~ 如果还有什么问题，随时可以再来问我哦！一起享受AC的快乐吧！