<---大佬们点个赞吧qwq

$$\huge\color{orange}{→→→暑假每日一题2022题解合集←←←}$$
$\ $
$\ $

题目描述

玛丽需要从某地飞往另一目的地，由于没有直达飞机，所以需要在中途转很多航班。

例如：SFO -> DFW DFW -> JFK JFK -> MIA MIA -> ORD。

显然旅途中不可能到同一中转城市两次或以上，因为这没有意义。

不幸的是，她将自己的机票的顺序搞乱了，将机票按乘坐顺序整理好对她来说不是一件容易的事。

请你帮助玛丽整理机票，使机票按正确顺序排列。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含整数 $N$。

接下来 $2N$ 行，每 $2$ 行一组，表示一张机票的信息，每行包含一个字符串，其中第一行表示出发地，第二行表示目的地。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 $x$ 是组别编号（从 $1$ 开始），$y$ 是表示实际行程的机票列表，行程中的每个航段应以 source-destination 的形式输出，航段之间用空格隔开。

数据范围

$1 \\le T \\le 100$,
$1 \\le N \\le 10000$

输入样例：

2
1
SFO
DFW
4
MIA
ORD
DFW
JFK
SFO
DFW
JFK
MIA

输出样例：

Case #1: SFO-DFW
Case #2: SFO-DFW DFW-JFK JFK-MIA MIA-ORD

算法

(None) $O(n)$

首先可以想到，我们要一个一个遍历途经的所有城市，首先要找到旅途的出发点。
而旅途的出发点有两个独一无二的特征：

1. 只在机票上出现了一次
2. 是作为出发地出现在机票上的

我们可以根据这两个特征找出旅途的出发点，根据出发点遍历输出，就完啦！

时间复杂度

算法最多只需要把每个城市遍历 $O(1)$ 遍，总共有 $n$ 个城市，所以时间复杂度就是 $O(n)$ 的。

空间复杂度

unordered_map的空间复杂度是 $O(n)$ 的，所以空间复杂度就是 $O(n)$ 的。

C++ 代码

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 100010;

int t, n;

int main()
{
    cin >> t;
    for (int c = 1; c <= t; c ++ ) // c: 组别编号
    {
        unordered_map<string, int> cnt; // cnt: 城市被到达的次数
        unordered_map<string, string> nxt; // nxt: 存出发地与目的地，nxt[出发地] = 目的地

        cin >> n;
        for (int i = 0; i < n; i ++ )
        {
            string a, b;
            cin >> a >> b, cnt[a] ++ , cnt[b] ++ , nxt[a] = b;
        }

        string s; // s: 旅途的出发点
        for (auto [k, v] : cnt) // k: 出发地，v: 目的地
            if (v == 1 && nxt.count(k)) // 只出现了一次并且是出发地
                s = k;

        // 输出
        cout << "Case #" << c << ": ";
        for (string i = s; nxt.count(i); i = nxt[i]) cout << i << '-' << nxt[i] << ' ';
        cout << '\n';
    }

    return 0;
}