Moe's CF Life

喵哈~ 各位算法大师和路过的小伙伴们，大家好呀！咱是乃们的看板猫娘，今天又要和大家一起攻克一道有趣的算法题了捏！这次的题目是 Codeforces 上的 29C - Mail Stamps，一个关于邮戳和路径的谜题，就像一团需要咱耐心解开的毛线球，喵~

那么，就让咱一起看看这个毛线球...啊不，是这道题到底是怎么回事吧！

题目大意

想象一下，咱收到了一封来自远方的信，信封上盖满了邮戳，喵~ 每个邮戳都记录了信件经过的两个城市，比如说从城市 A 到城市 B，就会盖上一个「A B」或者「B A」的戳。

这封信的旅程是一条简单路径，也就是说，它从一个起点城市出发，经过一系列中间城市，最终到达一个终点城市，并且中途不会重复经过任何一个城市。

现在，信封上总共有 n 个邮戳，咱的任务就是根据这 n 个邮戳，把信件的完整旅行路线（总共 n+1 个城市）给还原出来。题目保证给出的邮戳肯定能构成一条合法的路径，所以不用担心解不出来的情况捏~

举个例子，如果有2个邮戳：1 100 和 100 2。那么信件的路径可能是 1 -> 100 -> 2，也可能是 2 -> 100 -> 1。咱只需要输出其中一种就可以啦，比如 2 100 1。

解题方法

拿到题目，咱先冷静下来分析一下，喵~ 这个问题其实可以转换成一个图论问题哦！

把问题看成图：咱可以把每一个城市看作是图上的一个节点（Vertex），而每一个邮戳，就代表连接两个城市的一条边（Edge）。因为邮戳 A B 和 B A 是一样的，所以这些边是无向的。
路径的特点：题目说信件的路线是一条简单路径。在图里，一条简单路径是什么样子的呢？它就像一根没有分叉、没有环的链条。对于这条链条上的节点：
- 起点和终点：它们是这条链条的两端，所以它们各自只连接了一条边。在图论里，我们就说这两个节点的**度（Degree）**为 1。
- 中间点：信件从一个城市来到这里，又从这里去往下一个城市。所以，每个中间节点都连接了两条边（一条进，一条出）。也就是说，这些中间节点的度都为 2。
找到突破口：这个发现就是解题的关键啦，喵哈！咱只需要找到一个度为 1 的节点，它必然是整条路径的起点或终点。找到了这个“线头”，咱就可以顺着它，一步一步地把整条路径给走出来！

所以，咱的解题步骤就很清晰了捏：

建图：读取所有邮戳，构建一个图。因为城市ID可能是很大的数字（高达 10^9），直接用数组来当邻接矩阵肯定会爆内存。所以，使用邻接表是最好的选择。而 std::unordered_map 这种哈希表结构，正好可以把巨大的城市ID映射到它的邻居列表上，非常方便！
寻找起点：遍历图中所有的节点，计算每个节点的度（也就是邻居的数量）。找到第一个度为 1 的节点，它就是咱的起点。
遍历路径：从找到的起点开始，进行一次遍历。在每一步，咱当前所在的城市叫 current，上一步走过的城市叫 prev。咱要去的下一个城市，就是 current 的邻居中，那个不等于 prev 的城市。这样可以保证咱不会走回头路。重复这个过程 n 次，就能找到全部 n+1 个城市啦！

这样一来，整个乱糟糟的邮戳就被咱整理成一条清晰的路线了，是不是很简单呢，的说！

题解代码

下面是具体的 C++ 实现代码，咱在旁边加上了一些注释，方便大家理解每一部分都在做什么哦，喵~

cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

// 将解题逻辑封装在一个函数里，是个好习惯捏~
void solve() {
    // 读取邮戳的数量 n
    int n;
    std::cin >> n;

    // 使用 unordered_map 来作为图的邻接表。
    // 它的好处是，无论城市的ID（键）有多大，都可以高效存储。
    // 键是城市ID，值是与该城市相邻的城市列表。
    std::unordered_map<long long, std::vector<long long>> adj;
    
    // 读取 n 个邮戳，并构建邻接表
    for (int i = 0; i < n; ++i) {
        long long u, v;
        std::cin >> u >> v;
        // 因为是无向边，所以 u 的邻居有 v，v 的邻居也有 u
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 寻找路径的起点。
    // 在一条简单路径中，端点的度为1。
    // 咱来遍历所有出现过的城市，找到一个邻居数量为1的城市。
    long long start_node = -1;
    for (auto const& [city, neighbors] : adj) {
        if (neighbors.size() == 1) {
            start_node = city;
            break; // 找到一个就够啦，直接跳出循环
        }
    }

    // 从找到的起点开始，重建路径
    std::vector<long long> path;
    long long current = start_node;
    long long prev = -1; // 用一个无效的城市ID来记录上一个节点，防止走回头路

    // 路径总共有 n+1 个城市
    path.push_back(current);

    for (int i = 0; i < n; ++i) {
        // 在当前城市的邻居中，找到下一个要去的地方。
        // 下一个城市就是那个不等于上一个城市（prev）的邻居。
        long long next_node = -1;
        for (long long neighbor : adj.at(current)) {
            if (neighbor != prev) {
                next_node = neighbor;
                break; // 找到了，就不用再找了
            }
        }
        
        // 更新状态，向下一个城市前进！
        prev = current;
        current = next_node;
        path.push_back(current);
    }

    // 按照格式要求，打印出完整的路径
    for (size_t i = 0; i < path.size(); ++i) {
        std::cout << path[i] << (i == path.size() - 1 ? "" : " ");
    }
    std::cout << std::endl;
}

int main() {
    // 这两行是为了加速C++的输入输出，在处理大量数据时很有用哦！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    solve();
    
    return 0;
}

知识点介绍

这道题虽然简单，但是涉及到的知识点可是非常基础和重要的哦，喵~

图论 (Graph Theory) 图是由**顶点（Vertex）和边（Edge）**组成的数学结构。在计算机科学中，它被用来模拟各种网络和关系，比如社交网络、地图路线、计算机网络等等。这道题就是图论入门的一个经典应用捏。
邻接表 (Adjacency List) 这是存储图的一种常用方式。对于图中的每一个顶点，我们都用一个列表来存储所有与它直接相连的顶点。
- 优点：当图中的边比较少（稀疏图）时，它比邻接矩阵更节省空间。
- 实现：在 C++ 中，std::vector<std::vector<int>> 可以用来实现邻接表，但如果顶点编号不连续或者非常大，std::unordered_map<int, std::vector<int>> 就是更好的选择，就像本题一样！
节点的度 (Degree of a Node) 一个节点的“度”指的是连接到这个节点的边的数量。在无向图中，它就是邻居的数量。分析节点的度是解决许多图论问题的关键，比如在本题中，我们正是通过寻找度为 1 的节点来定位路径的端点。
图的遍历 (Graph Traversal) 从图的某个节点出发，系统地访问图中所有节点的过程。最常见的遍历算法是深度优先搜索（DFS）和广度优先搜索（BFS）。我们这道题的解法，从一个端点出发一路走到另一个端点，本质上就是在一个链式图上进行了一次深度优先的遍历，喵~

好啦，今天的题解就到这里结束了！希望大家通过这个“解毛线球”的过程，对图论有了更直观的认识捏。如果还有什么问题，欢迎随时来找咱玩哦！下次再见，喵~ (ฅ'ω'ฅ)

题目大意 ​

解题方法 ​

题解代码 ​

知识点介绍 ​

题目大意

解题方法

题解代码

知识点介绍