InterestingComputerGame - 题解

标签与难度

标签: 图论, 并查集, 离散化, 数据结构, 图的连通分量, 思维, 贪心

难度: 1600

题目大意喵~

你好呀，指挥官！阿波罗正在玩一个有趣的游戏，一共有 N 个回合。在第 i 回合，电脑会给出两个整数 $(a_i, b_i)$ 。阿波罗在这一回合可以做下面三件事中的一件：

什么都不做。
如果数字 $a_i$ 之前没被选过，就选择它。
如果数字 $b_i$ 之前没被选过，就选择它。

阿波罗已经知道了所有 N 回合的数字对，他想知道，采取最优策略，最多能选择多少个不同的数字呢？

简单来说，我们有 N 次机会，每次机会都与一对数字 $(a_i, b_i)$ 关联。每次机会，我们可以用它来“解锁” $a_i$ 或者 $b_i$ （如果它们还没被解锁的话），或者放弃这次机会。目标是最大化解锁的数字总数，喵~

解题思路分析

这道题看起来是在做选择，但其实可以把它想象成一个有趣的连线游戏哦，喵！我们可以把问题转化成一个图论模型来解决，这样思路就清晰多啦！

1. 建立图模型

我们可以把每一个出现过的数字看作图上的一个节点（Vertex）。而每一回合给出的数字对 $(a_i, b_i)$ ，就可以看作是连接节点 $a_i$ 和节点 $b_i$ 的一条边（Edge）。

这样一来，整个问题就变成：我们有一个图，图上有若干个节点和 N 条边。每一条边都代表一次选择机会，我们可以用这条边来“激活”它的两个端点之一。我们的目标是激活尽可能多的节点。

2. 分析连通分量

这个图可能会分成好几个互不相连的部分，我们称之为连通分量。在一个连通分量里做的选择，完全不会影响到另一个连通分量，对吧？所以我们可以分开考虑每一个连通分量，最后把结果加起来！

现在，我们来揪住一个连通分量，分析一下能选多少个节点。假设这个连通分量里有 V 个节点（代表 V 个不同的数字）和 E 条边（代表 E 次选择机会）。

情况一：这个连通分量是一棵树 (Tree) 一棵树的特点是，它的边数 E 总是比顶点数 V 少 1，也就是 $E = V - 1$ 。这意味着我们有 $V-1$ 次选择机会，却要从 V 个节点中挑选。就像有 $V-1$ 份猫罐头要分给 V 只我，总有一只我会吃不到的，呜... T_T 所以，在这种情况下，我们最多只能选择 $V-1$ 个节点。我们可以随便指定一个节点当树根，然后用每一条连接父子节点的边去选择那个子节点，这样除了根节点外，其他 $V-1$ 个节点都能被选中。
情况二：这个连通分量包含环 (Cycle) 如果一个连通图不是树，那它一定有环。有环的充要条件是 $E \ge V$ 。这意味着我们的选择机会（边的数量 E）至少和要选择的目标（节点的数量 V）一样多！我们有足够多的机会，是不是就能把所有 V 个节点都选上呢？是的，喵！我们可以先在连通分量里找一棵生成树，这棵生成树有 V 个节点和 $V-1$ 条边。像刚才那样，用这 $V-1$ 条边先选好 $V-1$ 个节点。因为 $E \ge V$ ，所以我们至少还多出来一条边。这条多出来的边连接着生成树里的两个节点，它正好可以用来选择那个我们之前没选上的根节点！所以，只要有环，我们就能把这个连通分量里的所有 V 个节点都选上！

3. 算法实现：并查集大法！

要把这个思路变成代码，我们需要解决两个问题：

怎么知道哪些节点在同一个连通分量里？
怎么判断一个连通分量里有没有环？

这简直是为**并查集（Disjoint Set Union, DSU）**量身定做的问题，喵！

我们可以用并查集来维护这些连通分量。并查集里的每个集合就对应一个连通分量。在处理每一条边 $(u, v)$ 时：

如果 u 和 v 已经在同一个集合里了（用 find(u) == find(v) 判断），说明在连接它俩之前，它们就已经连通了。现在再加一条边，必然会形成一个环！我们就给这个连通分量打上一个“有环”的标记。
如果 u 和 v 不在同一个集合，我们就把它们合并（union），这代表我们连接了两个原本独立的区域。

为了实现这个，我们的并查集需要维护三个信息：

parent[i]: 节点 i 的父节点。
component_size[i]: 以 i 为根的集合的大小（即连通分量的节点数）。
has_cycle[i]: 以 i 为根的连通分量是否包含环。

4. 离散化

题目中的数字可能很大（比如 $10^9$ ），但总的数字个数最多只有 $2N$ 。我们不能开那么大的数组呀！所以需要离散化。先把所有出现过的数字收集起来，排序去重，然后用它们在排序后数组中的下标（0, 1, 2...）来代表原来的数字。这样就把大大的数字映射到了小小的、连续的整数索引上啦！

总结一下步骤：

读入数据：读取所有 N 个数对。
离散化：将所有出现的数字进行离散化处理，得到一个从原始数字到新索引的映射。
初始化并查集：为每个唯一数字（的新索引）初始化一个集合，大小为1，没有环。
构建图与分析：遍历 N 个数对（边），用并查集进行合并。在合并过程中，记录每个连通分量的节点数，并检测是否出现环。
计算结果：遍历所有连通分量（即并查集中的每个根节点），根据它是否有环，将该分量的节点数（如果有环）或节点数减一（如果是树）累加到最终答案中。

这样，我们就能高效地解决问题啦，是不是很清晰呢？喵~

代码实现

这是我根据上面的思路，精心重构的一份代码哦！注释很详细，希望能帮到你，呐~

cpp

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

// DSU (并查集) 的相关数据
// parent[i] 存储节点 i 的父节点
std::vector<int> parent;
// component_size[i] 存储以 i 为根的连通分量中的节点数量
std::vector<int> component_size;
// has_cycle[i] 标记以 i 为根的连通分量是否包含环
std::vector<bool> has_cycle;

// 并查集的 find 操作，带路径压缩
int find_set(int v) {
    if (v == parent[v]) {
        return v;
    }
    return parent[v] = find_set(parent[v]);
}

// 并查集的 union 操作
void unite_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        // 按大小合并，小的合并到大的，可以略微优化性能
        if (component_size[a] < component_size[b]) {
            std::swap(a, b);
        }
        parent[b] = a;
        component_size[a] += component_size[b];
        // 如果被合并的集合中有一个有环，那么新集合也有环
        has_cycle[a] = has_cycle[a] || has_cycle[b];
    } else {
        // 如果 a 和 b 已经在同一个集合，再加一条边就会形成环
        has_cycle[a] = true;
    }
}

void solve(int case_num) {
    int n;
    std::cin >> n;
    std::vector<std::pair<int, int>> edges(n);
    std::vector<int> all_numbers;
    all_numbers.reserve(2 * n);

    // 1. 收集所有数字用于离散化
    for (int i = 0; i < n; ++i) {
        std::cin >> edges[i].first >> edges[i].second;
        all_numbers.push_back(edges[i].first);
        all_numbers.push_back(edges[i].second);
    }

    // 2. 离散化
    std::sort(all_numbers.begin(), all_numbers.end());
    all_numbers.erase(std::unique(all_numbers.begin(), all_numbers.end()), all_numbers.end());

    int num_unique_nodes = all_numbers.size();
    auto get_id = [&](int val) {
        return std::lower_bound(all_numbers.begin(), all_numbers.end(), val) - all_numbers.begin();
    };

    // 3. 初始化并查集
    parent.resize(num_unique_nodes);
    std::iota(parent.begin(), parent.end(), 0); // parent[i] = i
    component_size.assign(num_unique_nodes, 1);
    has_cycle.assign(num_unique_nodes, false);

    // 4. 处理每一条边，构建连通分量并检测环
    for (const auto& edge : edges) {
        int u = get_id(edge.first);
        int v = get_id(edge.second);
        unite_sets(u, v);
    }

    // 5. 计算最终答案
    int max_selected_count = 0;
    for (int i = 0; i < num_unique_nodes; ++i) {
        // 如果 i 是一个连通分量的根节点
        if (parent[i] == i) {
            if (has_cycle[i]) {
                // 如果有环，可以选择该分量中的所有节点
                max_selected_count += component_size[i];
            } else {
                // 如果是树，只能选择 V-1 个节点
                max_selected_count += component_size[i] - 1;
            }
        }
    }

    std::cout << "Case #" << case_num << ": " << max_selected_count << std::endl;
}

int main() {
    // 加速输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
    }

    return 0;
}

复杂度分析

时间复杂度: $O(T \cdot N \log N)$ ，其中 T 是测试用例的数量。对于每个测试用例，主要的时间开销在于：
1. 离散化：收集 $2N$ 个数字，排序需要 $O(N \log N)$ 。
2. 并查集操作：处理 N 条边。带路径压缩和按大小（或秩）合并的并查集，每次操作的平均时间复杂度接近常数，记为 $O(\alpha(N))$ ，其中 $\alpha$ 是反阿克曼函数，增长极其缓慢。总共是 $O(N \cdot \alpha(N))$ 。
3. 计算答案：遍历所有唯一节点，需要 $O(N)$ 。因此，总的时间复杂度由排序主导，为 $O(N \log N)$ 。
空间复杂度: $O(N)$ 。我们需要存储：
1. edges 数组： $O(N)$ 。
2. all_numbers 向量：最多 $2N$ 个数字，所以是 $O(N)$ 。
3. 并查集的三个数组 (parent, component_size, has_cycle)：大小都是唯一节点的数量，最多 $2N$ ，所以是 $O(N)$ 。总空间复杂度为 $O(N)$ 。

知识点总结

这道题真是一次愉快的思维探险呢，喵！我们用到了几个非常核心的算法知识点：

图论建模：将看似无关的选择问题抽象成图的节点和边，是解决很多问题的关键第一步。
离散化：当问题中数值范围很大但数量不多时，离散化是一种标准且高效的预处理技巧。
并查集 (DSU)：处理动态连通性问题的超级利器！它能高效地完成集合的合并与查询，非常适合用来找连通分量。
在并查集中检测环：通过检查待合并的两个元素是否已在同一集合，可以轻松判断加边操作是否会形成环。这是并查集的一个经典应用。
分类讨论：根据连通分量的结构（是树还是有环图）来决定最优策略，体现了算法的灵活性。

希望这篇题解能让你对这些知识点有更深的理解，如果还有问题，随时可以再来问我哦！一起加油，喵~！

InterestingComputerGame - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

1. 建立图模型 ​

2. 分析连通分量 ​

3. 算法实现：并查集大法！ ​

4. 离散化 ​

总结一下步骤： ​

代码实现 ​

复杂度分析 ​

知识点总结 ​