E. Round Dance - 题解

比赛与标签

比赛: Codeforces Round 874 (Div. 3) 标签: dfs and similar, dsu, graphs, shortest paths 难度: *1600

喵喵，我们来跳舞吧！(题目大意)

在一个盛大的节日上，有 n 位小伙伴决定一起跳圆圈舞！一个合格的圆圈舞，里面至少要有 2 个人，而且每个人都恰好有两个邻居。

现在，我们只知道每个小伙伴 i 都只记得他的一个邻居 a[i]。根据这些零碎的信息，我们需要推断出，这 n 个人最少可以组成多少个圆圈舞，以及最多可以组成多少个圆圈舞呢？

举个栗子，如果有6个人，他们记得的邻居分别是 [2, 1, 4, 3, 6, 5]。

• 最多可以有 3 个舞团：1-2-1，3-4-3，5-6-5。
• 最少可以有 1 个舞团：把所有人都串起来 1-2-3-4-5-6-1。

我们的任务就是对给定的输入，输出这个最小值和最大值，喵~

把跳舞变成图论游戏喵~ (解题思路)

初看这个问题可能会觉得有点复杂，但只要我们把它转换成一个熟悉的模型，一切就豁然开朗啦！这种“谁和谁有关联”的问题，最适合用图论来解决了，的说！

1. 建模：每个人都是一个点

我们可以把 n 个小伙伴看作是图上的 n 个节点。题目说“第 i 个人记得邻居 a[i]”，我们就可以把它看作是一条从节点 i 指向节点 a[i] 的有向边。

2. 图的结构：一堆漂亮的圈圈

因为每个人都只记得一个邻居，所以从每个节点出发，都只有一条出边（出度为1）。这种每个点出度都为1的图，我们称之为函数图 (Functional Graph)。

函数图有一个非常美妙的性质：从任何一个点开始沿着边走，最终必然会进入一个环。因为题目保证了每个人都能参与圆圈舞，这意味着图中的每个节点都必须在一个环上。所以，整个图其实就是由若干个互不相交的简单环组成的！我们的问题就变成了：找出这个图里有多少个独立的环。

3. 寻找组件：找圈圈大作战！

怎么找到这些环呢？我们可以遍历从 0 到 n-1 的每个节点。如果一个节点 i 还没有被访问过，就说明我们发现了一个新的、未知的组件（也就是一个新的环）。从这个节点 i 出发，我们就可以找到它所在的整个环。

一个非常经典的找环算法是弗洛伊德的龟兔赛跑算法 (Floyd's Tortoise and Hare Algorithm)。

• 我们设置两个指针，一个叫 slow (乌龟)，一个叫 fast (兔子)，都从节点 i 出发。
• slow 每次走一步 (slow = a[slow])。
• fast 每次走两步 (fast = a[a[fast]])。
• 如果图中存在环，fast 最终一定会在环里追上 slow！当 slow == fast 时，我们就成功找到了一个环。

找到环之后，我们把环上所有的节点都标记为 visited，这样就不会重复计算啦。

4. 计算最大值：最多能有多少个舞团？

这个最简单了，喵~ 既然我们把图分成了好几个独立的环，那么每个环都可以自己形成一个独立的圆圈舞。所以，最大舞团数就等于我们找到的环的总数。

5. 计算最小值：最少能有多少个舞团？

这个稍微需要动动脑筋，呐。我们想让舞团数量尽可能少，就要想办法把不同的环合并成一个大环。

• “长链环” (长度 > 2): 比如 1->2->3->1。这种环里的三个人关系是固定的，1 必须和 3、2 做邻居。我们没法把它拆开或者和其他环合并，否则就会破坏原有的邻居关系。所以，这种长度大于2的环是“锁死的”，它们必须各自形成一个舞团。
• “互惠环” (长度 = 2): 比如 1->2->1。这种两个人互为邻居的环就非常灵活了！它们可以自己组成一个两人舞团。但是，我们也可以把它们“打开”，和其他的“互惠环”串联起来。比如，我们有 (1,2) 和 (3,4) 两个互惠环，我们可以把它们合并成一个更大的舞团 1-2-3-4-1！

所以，最小化策略就是：

1. 所有长度大于2的“长链环”都各自算作一个舞团。
2. 把所有长度为2的“互惠环”全部串联起来，合并成一个超大的舞团。
3. 因此，最小舞团数 = (长链环的数量) + (1, 如果存在互惠环的话)。

换个方式说就是：最小舞团数 = (总环数) - (互惠环数) + 1 (当然，前提是互惠环数 > 0)。如果一个互惠环都没有，那最小值就和最大值一样，等于总环数。

让代码跳起舞来~ (代码实现)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 提高输入输出效率，让程序跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        // 读取每个人的邻居，并转换为0-based索引，方便数组操作
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            a[i]--; // C++数组从0开始，题目输入从1开始
        }

        // in_degree 在当前AC代码中没有被使用，可以忽略~
        vector<int> in_degree(n, 0);
        for (int i = 0; i < n; i++) {
            in_degree[a[i]]++;
        }

        // visited数组用来标记一个节点是否已经被某个环处理过
        vector<bool> visited(n, false);
        int cycles = 0;         // 总的环数量
        int mutual_cycles = 0;  // 长度为2的环（互惠环）的数量

        // 遍历所有节点，寻找未被访问的组件（环）
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue; // 如果已经访问过，就跳过

            // 使用Floyd龟兔赛跑算法来检测环
            int slow = i;
            int fast = i;
            bool cycle_found = false;

            while (true) {
                slow = a[slow];      // 乌龟走一步
                fast = a[a[fast]]; // 兔子走两步
                if (slow == fast) {
                    cycle_found = true; // 相遇了，说明在环里！
                    break;
                }
                // 如果任意一个指针进入了之前已发现的环，就停止
                // 在本题中，因为组件都是独立的环，这个条件其实不会被以这种方式触发
                // 但这是写健壮的函数图代码的好习惯
                if (visited[slow] || visited[fast]) break;
            }

            if (cycle_found) {
                // 找到了一个新环！
                cycles++;
                
                // 现在我们需要遍历这个环，标记所有节点，并计算环的长度
                vector<int> cycle_nodes;
                int cur = slow; // 从相遇点开始
                do {
                    cycle_nodes.push_back(cur);
                    visited[cur] = true; // 标记为已访问
                    cur = a[cur];
                } while (cur != slow); // 走一圈回到原点

                // 判断是不是长度为2的互惠环
                if (cycle_nodes.size() == 2) {
                    mutual_cycles++;
                }
            } else {
                // 这部分代码处理从当前节点i出发，最终进入一个已访问过的环的情况
                // 在本题中不会发生，因为所有组件都是独立的环
                int cur = i;
                while (!visited[cur]) {
                    visited[cur] = true;
                    cur = a[cur];
                }
            }
        }

        // 计算最大舞团数：就是环的总数
        int max_dances = cycles;
        // 计算最小舞团数：(总环数 - 互惠环数) + (1个由所有互惠环合并成的大环)
        // 如果没有互惠环，那就还是总环数
        int min_dances = (mutual_cycles > 0) ? (cycles - mutual_cycles + 1) : cycles;

        cout << min_dances << " " << max_dances << '\n';
    }
    return 0;
}

跳舞要多久喵？(复杂度分析)

• 时间复杂度: O(n) 的说。 我们有一个外层循环遍历所有 n 个节点。在循环内部，每个节点只会被龟兔赛跑算法和后续的标记过程访问一次。因此，每个节点和每条边都只会被处理常数次，总的时间复杂度就是线性的，O(n)。

• 空间复杂度: O(n) 的说。 我们使用了 a 数组、visited 数组等来存储信息，它们的大小都和 n 成正比。所以空间复杂度也是 O(n)。

这次学会了什么新舞步？(知识点与总结)

这道题真是太有趣啦，它教会了我们好多东西呢！

1. 图论建模: 核心技巧！将看似复杂的人际关系问题，转化为清晰的图论模型，是解决这类问题的关键第一步。
2. 函数图 (Functional Graph): 认识到“每个点出度为1”这个特性，就能推断出图是由若干个环和指向环的树组成的结构。在本题中，它被简化为只由环组成。
3. 环检测算法: Floyd的龟兔赛跑算法 是一个不使用额外栈空间（相比DFS）就能在O(n)时间内找到环的优雅算法，非常实用！
4. 分类讨论思想: 解题的关键在于区分“长链环”和“互惠环”，并分析它们在组合时的不同性质。这是决定最小舞团数的关键。

希望这篇题解能帮助主人更好地理解这道题目！继续加油，算法的世界还有更多有趣的冒险等着我们去探索，喵~！(๑•̀ㅂ•́)و✧