喵~ 主人 sama，下午好呀！今天有 n 个小朋友在围着圣诞树跳舞哦，他们手拉手转圈圈，好可爱呀~ 可是跳完舞他们只记得自己后面两个人是谁了，顺序还忘了，真是群迷糊的小家伙呢。主人能帮他们重新排好队嘛？让本喵来带你一步步解开这个谜题吧！

题目大意

题目是这样子的喵：有 n 个小朋友，编号从 1 到 n，他们围成一个圈。我们把顺时针的顺序记作一个排列 p = [p_1, p_2, ..., p_n]。每个小朋友 p_i 的下一个是 p_{i+1}（如果 i=n，下一个就是 p_1）。

跳完舞之后，每个小朋友 i 都只记得两个人：他顺时针方向的下一个人（我们叫他 x），以及 x 的下一个人。也就是说，小朋友 i 记得 {next(i), next(next(i))}。

但是，他们告诉我们这两个人时，顺序是随机的。比如小朋友 i 记得 a_{i,1} 和 a_{i,2}，我们只知道 {a_{i,1}, a_{i,2}} = {next(i), next(next(i))}，但不知道哪个是哪个。

我们的任务就是根据这些信息，把小朋友们的圆圈顺序 p 给还原出来。题目保证一定有解，而且任何一个正确的圈圈顺序都可以哦（比如从谁开始都行）。

题解方法

这个问题看起来像是在一团乱麻里找线头，但其实只要找到一个头，就能把整个线团解开啦，喵~ 我们的思路就像是在玩一个叫做‘接龙’的游戏。

首先，我们随便找一个小朋友当起点，比如说 1 号小朋友。让他当队伍的第一个人，p[0] = 1。因为是圆圈，所以从谁开始都无所谓啦。

现在，我们需要找到队伍里的第二个人 p[1]。1 号小朋友记得两个人，我们叫他们 u 和 v 好了。这两个人中，一个是 p[1]（1号的下家），另一个是 p[2]（1号下家的下家）。我们怎么分清谁是谁呢？

这里有个关键的小窍门哦！ 假设队伍的顺序是 1 -> p[1] -> p[2] -> ...

• 1 号小朋友记得 {p[1], p[2]}。
• p[1] 号小朋友应该记得 {p[2], p[3]}。

如果我们假设 p[1] 是 u，那么 p[2] 就得是 v。这意味着，u 的下一个小朋友是 v。那么 u 小朋友自己应该记得 {v, v的下一个}。所以，u 记得的人里面一定有 v！

反过来，如果我们假设 p[1] 是 v，那么 p[2] 就得是 u。这意味着 v 的下一个是 u，所以 v 记得的人里面一定有 u！

因为题目保证有解，所以这两种情况肯定只有一个成立。所以，我们只需要检查一下：u 记得的人里有 v 吗？

• 如果有，那么队伍顺序就是 1 -> u -> v -> ...，所以 p[1] = u。
• 如果没有，那队伍顺序就一定是 1 -> v -> u -> ...，所以 p[1] = v。

耶！我们成功找到了队伍里的第二个人 p[1]！

那第三个、第四个...直到最后一个人怎么找呢？ 其实更简单了！一旦我们知道了队伍里的前两个人 p[i-2] 和 p[i-1]，我们就能立刻知道 p[i] 是谁。 因为 p[i-2] 小朋友记得 {p[i-1], p[i]}。我们已经知道了 p[i-1]，那 p[i-2] 记得的另一个人，不就是 p[i] 嘛！

所以，我们的完整步骤就是：

1. 钦定 p[0] = 1。
2. 找到 1 号记得的两个人 u 和 v。通过检查 u 是否记得 v，来确定 p[1] 是 u 还是 v。
3. 从 i = 2 开始循环到 n-1：
   • p[i] 就是 p[i-2] 记得的两个人中，不是 p[i-1] 的那一个。
4. 这样一步步下去，整个队伍就排好啦！是不是很简单呢，nyaa~

题解

主人请看，这段 C++ 代码就是按照我们刚才的思路写的哦~

#include <iostream>
#include <vector>
#include <utility>

int main() {
    // 使用快速 I/O 让程序跑得更快一点，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // remembered_by[i] 存储了第 i 个小朋友记得的那两个人
    // 我们用 1-based 索引，所以数组大小是 n+1，这样和题目编号对应起来比较方便
    std::vector<std::pair<int, int>> remembered_by(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> remembered_by[i].first >> remembered_by[i].second;
    }

    // p 数组用来存放我们最终找到的队伍顺序
    std::vector<int> p(n);

    // 任意选择一个起点，我们就从 1 号小朋友开始吧！
    p[0] = 1;

    // 1 号小朋友记得的两个人是 u 和 v
    // 其中一个是队伍里的第2个，另一个是第3个
    int u = remembered_by[p[0]].first;
    int v = remembered_by[p[0]].second;

    // 这里就是我们刚才说的关键判断啦！
    // 如果 u 记得 v，说明队伍顺序是 1 -> u -> v ...
    // 那么队伍的第二个人就是 u
    if (remembered_by[u].first == v || remembered_by[u].second == v) {
        p[1] = u;
    } else {
        // 否则，顺序一定是 1 -> v -> u ...
        // 队伍的第二个人就是 v
        p[1] = v;
    }

    // 现在我们已经确定了 p[0] 和 p[1]，可以愉快地接龙了！
    // 从 i=2 开始，依次找出 p[2], p[3], ...
    for (int i = 2; i < n; ++i) {
        int prev_kid = p[i - 2]; // 队伍里的上上个小朋友
        int curr_kid = p[i - 1]; // 队伍里的上一个小朋友

        // prev_kid 记得 {curr_kid, p[i]}
        // 所以我们检查 prev_kid 记得的两个人
        // 如果第一个是 curr_kid，那第二个就是 p[i]
        if (remembered_by[prev_kid].first == curr_kid) {
            p[i] = remembered_by[prev_kid].second;
        } else {
            // 否则，第一个就是 p[i]
            p[i] = remembered_by[prev_kid].first;
        }
    }

    // 找到完整的队伍啦，把结果打印出来~
    for (int i = 0; i < n; ++i) {
        std::cout << p[i] << (i == n - 1 ? "" : " ");
    }
    std::cout << '\n';

    return 0;
}

知识点介绍

通过解决这个可爱的问题，我们还顺便复习了一些有趣的知识点呢，喵！

1. 排列 (Permutation) 这个问题本质上是要求我们找出一个符合条件的 1 到 n 的排列。排列就是把一组对象进行排序。这里的“圆圈舞”意味着排列是循环的，比如 [1, 2, 3, 4, 5] 和 [3, 4, 5, 1, 2] 在这个问题里是等价的解。

2. 图论 (Graph Theory) 虽然我们没有显式地画图，但可以把这个问题看作一个图论问题。每个小朋友是一个节点。小朋友 i 和他的下一个 next(i) 之间有一条有向边 i -> next(i)。所有这些边构成了一个大圈圈（一个有向环）。题目给我们的信息是，对于每个节点 i，我们知道它指向的节点 i->next 和下下个节点 i->next->next，但不知道哪个是哪个。我们的任务就是根据这些“长度为2的路径”信息，重建整个环。

3. 贪心算法 (Greedy Algorithm) 我们的解法是一种贪心策略。在每一步，我们都根据当前已知的信息做出一个确定的、局部最优的选择，而没有进行回溯。我们先固定一个起点，然后用确定的逻辑推导出第二个点，再用前两个点推导出第三个点……每一步都是唯一的、不可更改的。因为题目保证有解，所以这种贪心的“一条路走到底”的策略是可行的，并且能高效地找到答案。

希望本喵的讲解对主人有帮助哦！下次再遇到有趣的题目，再来一起玩吧！Nyaa~ (ฅ'ω'ฅ)