Moe's CF Life

Appearance

F. Asya And Kittens - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 541 (Div. 2) 标签: constructive algorithms, dsu 难度: *1700

题目大意喵~ ​

主人你好呀~！这道题是关于一群可爱的小猫咪的哦！(ฅ'ω'ฅ)

一开始，有 n 只小猫，每只猫咪都待在自己的小房间里。这 n 个房间排成一排。在接下来的 n-1 天里，每天都会有一对相邻房间的小猫 x 和 y 想要一起玩，于是它们之间的隔板就会被拆掉，两个房间合并成一个大房间。

经过 n-1 天后，所有的隔板都被拆掉了，所有的小猫都住在一个超级大的房间里啦！我们知道每天是哪两只小猫 x 和 y 凑到了一起，但我们不知道它们一开始是怎么排列的。

我们的任务就是，根据这 n-1 次合并的信息，找出一种可能的小猫初始排列方式，然后按顺序输出它们的名字（编号）就可以啦！

解题思路详解的说 ​

喵哈哈，这道题看起来就像是把一堆小东西不断合并起来，一看到“合并集合”，本喵的DNA就动了！这不就是并查集（DSU）最擅长的事情嘛！

但是呢，一个普普通通的并查集只能告诉我们哪些小猫在同一个大房间里，却没法告诉我们它们的相对顺序。题目要求我们输出一个完整的排列，所以我们需要给我们的并查集加一点“魔法”！✨

这个魔法就是，我们不仅要记录每个集合（也就是每个合并后的大房间）里有哪些猫，还要记录这个大房间里，排在最左边（链头）和最右边（链尾）的猫咪是谁！

让我们来梳理一下思路吧：

  1. 初始化:

    • 一开始，每只猫咪 i 都是一个独立的集合，它们自己就是自己的老大（代表元）。
    • 每只猫咪 i 也是自己所在“房间链”的链头和链尾。
    • 我们还需要一个方法来把猫咪们像串珠子一样串起来。可以用一个 next_kitten 数组，next_kitten[i] 表示在猫咪 i 右边的下一只猫咪是谁。初始时，大家都是独立的，所以 next_kitten 都是空的（比如用 0 表示）。

  2. 合并操作:

    • 当题目告诉我们，猫咪 u 和猫咪 v 所在的房间合并了，我们就要进行一次并查集合并操作。
    • 首先，找到 u 和 v 所在集合的代表元，我们叫它们 root_u 和 root_v。
    • 现在，我们要把 root_u 代表的猫咪链和 root_v 代表的猫咪链连接起来。怎么连呢？很简单，把一条链的尾巴接在另一条链的头上就好啦！
    • 比如说，我们决定把 v 的链条接在 u 的链条后面。那么，u 链条的尾巴（tail_u）的下一个就是 v 链条的头（head_v）。我们就可以更新 next_kitten[tail_u] = head_v。
    • 连接完链条后，我们再执行标准的并查集合并。为了效率，最好使用“按秩合并”或“按大小合并”，这里我们用按大小合并，把小集合并到大集合里，这样能让我们的并查集树结构更扁平，查询更快哦！
    • 假设我们把 root_v 合并到 root_u。合并后，新的大集合的代表元是 root_u。这个新链条的链头还是原来 u 链条的链头，但链尾就变成了原来 v 链条的链尾啦！我们需要更新 root_u 所记录的链头和链尾信息。

  3. 最终输出:

    • 经过 n-1 次合并，所有的小猫咪都会被合并到同一个集合里。
    • 我们随便找一只猫咪（比如 1 号），找到它所在集合的最终代表元 final_root。
    • 从这个代表元记录的链头 start_node 开始，利用我们维护好的 next_kitten 数组，就像跳房子一样，一个接一个地把所有猫咪的名字打印出来，直到链条的末尾。这样，一个完整的初始排列就找到啦！

总的来说，我们就是用一个“带权”的并查集，这个“权”就是每个集合所代表的猫咪链的头和尾。每次合并，我们不仅合并集合，还把链条也连接起来，最终形成一条完整的猫咪长队！是不是很巧妙呀，喵~？

代码实现喵~ ​

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

// DSU的find操作，带有路径压缩优化，喵~
// 找到v所在集合的代表元
int find_set(int v, std::vector<int>& parent) {
    if (v == parent[v]) {
        return v;
    }
    return parent[v] = find_set(parent[v], parent);
}

int main() {
    // 关掉同步流，让输入输出更快一点，这样就不会TLETLE啦！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // --- 并查集数据结构 ---
    // parent[i]: 元素i的父节点
    std::vector<int> parent(n + 1);
    std::iota(parent.begin(), parent.end(), 0); // 初始化，每个元素都是自己的父节点
    // sz[i]: 以i为根的集合的大小（只对根节点有效）
    std::vector<int> sz(n + 1, 1);

    // --- 并查集的“权值”部分，用来维护链条信息 ---
    // chain_ends[i]: 存储以i为根的集合所代表的猫咪链的 {头, 尾}
    std::vector<std::pair<int, int>> chain_ends(n + 1);
    for (int i = 1; i <= n; ++i) {
        chain_ends[i] = {i, i}; // 初始化，每个链条只有一个猫咪
    }

    // next_kitten[i]: 存储在猫咪i右边的下一只猫咪是谁
    std::vector<int> next_kitten(n + 1, 0); // 0 表示链条的末尾

    // --- 处理n-1次合并 ---
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;

        int root_u = find_set(u, parent);
        int root_v = find_set(v, parent);

        // 按大小合并：总是把小的集合合并到大的集合里
        // 这样可以保证并查集树的深度尽量小，操作更快哦
        // 我们约定 root_u 是较大（或等大）集合的根
        if (sz[root_u] < sz[root_v]) {
            std::swap(root_u, root_v);
        }

        // 核心合并逻辑！我们把v所在的链条接到u所在的链条后面
        // 1. 连接两个链条
        // u链条的尾巴后面现在是v链条的头啦
        int tail_of_u_chain = chain_ends[root_u].second;
        int head_of_v_chain = chain_ends[root_v].first;
        next_kitten[tail_of_u_chain] = head_of_v_chain;

        // 2. 更新并查集数据：把v集合合并到u集合
        parent[root_v] = root_u;
        sz[root_u] += sz[root_v];

        // 3. 更新新合并链条的头和尾
        // 新链条由 root_u 代表
        // 它的头是原来u链的头，尾是原来v链的尾
        int head_of_u_chain = chain_ends[root_u].first;
        int tail_of_v_chain = chain_ends[root_v].second;
        chain_ends[root_u] = {head_of_u_chain, tail_of_v_chain};
    }

    // n-1次合并后，所有猫咪都在一个集合里了
    // 随便找一只猫（比如1号）来找到最终集合的根
    int final_root = find_set(1, parent);
    
    // 从最终根节点的元数据里，找到完整链条的起始猫咪
    int start_node = chain_ends[final_root].first;
    
    // 顺着next_kitten指针，遍历并打印整个链条
    int current = start_node;
    while (current != 0) {
        std::cout << current << " ";
        current = next_kitten[current];
    }
    std::cout << std::endl;

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(n * α(n)) 的说。 我们进行了 n-1 次合并操作。每次操作都包含几次 find_set 和一次合并。因为我们使用了路径压缩和按大小合并的优化，并查集的 find 和 union 操作的平均时间复杂度接近常数，严格来说是 O(α(n))，其中 α(n) 是反阿克曼函数，它增长得非常非常慢，对于所有实际可能的 n，它的值都不会超过 5。所以总的时间复杂度几乎是线性的，非常高效哦！

  • 空间复杂度: O(n) 的说。 我们需要几个大小为 n+1 的数组来存储并查集信息 (parent, sz) 和链条信息 (chain_ends, next_kitten)。所以空间开销是和猫咪数量 n 成正比的。

知识点与总结 ​

这道题真是一道非常经典的并查集应用题呢，喵~ 它教会了我们一个重要的思想：

  1. 带权并查集 (Augmented DSU): 当标准的并查集无法满足我们的需求时，可以考虑在集合的代表元上附加额外的信息（也就是“权值”）。在这个问题里，我们的“权值”就是链条的头和尾。

  2. 维护额外信息: 关键在于想清楚在合并两个集合时，如何合并它们各自的“权值”。在这里，就是把一条链的尾巴和另一条链的头连接起来，并更新新链的头尾。

  3. 链式结构表示: 使用一个 next 数组来表示一个链表（或者说序列）是非常常见的技巧。通过这个数组，我们可以在最后轻松地遍历出整个序列。

总之，遇到需要合并集合，并且还要维护集合内部某种结构（比如顺序、总和等）的问题时，都可以尝试用带权并查集的思路来解决！希望这篇题解能帮到你，加油哦，你一定可以的！(๑•̀ㅂ•́)و✧

Released under the MIT License.

Copyright © 2024-present Moe