摘要
Title: 693. 行程排序
Tag: 哈希表
Memory Limit: 64 MB
Time Limit: 1000 ms

693. 行程排序

题意

玛丽需要从某地飞往另一目的地，由于没有直达飞机，所以需要在中途转很多航班。
例如：SFO -> DFW DFW -> JFK JFK -> MIA MIA -> ORD。
显然旅途中不可能到同一中转城市两次或以上，因为这没有意义。
不幸的是，她将自己的机票的顺序搞乱了，将机票按乘坐顺序整理好对她来说不是一件容易的事。
请你帮助玛丽整理机票，使机票按正确顺序排列。
思路

哈希，链表输出即可

代码

/*
* @Author: NEFU AB-IN
* @Date: 2022-08-04 16:35:04
* @FilePath: \Acwing\693\693.cpp
* @LastEditTime: 2022-08-04 16:42:55
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(X) ((int)(X).size())
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(0);                                                                                                        \
    cout.tie(0)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int INF = INT_MAX;
const int N = 1e6 + 10;

signed main()
{
    IOS;
    int T;
    cin >> T;
    for (int _ = 1; _ <= T; ++_)
    {
        int n;
        cin >> n;
        map<string, string> st;
        map<string, int> deg;
        set<string> se;
        for (int i = 1; i <= n; ++i)
        {
            string s, t;
            cin >> s >> t;
            st[s] = t;
            deg[t]++;
            se.insert(s), se.insert(t);
        }

        string s;
        for (auto c : se)
        {
            if (!deg[c])
                s = c;
        }
        printf("Case #%lld: ", _);

        while (st.count(s))
        {
            printf("%s-%s ", s.c_str(), st[s].c_str());
            s = st[s];
        }
        puts("");
    }
    return 0;
}

693. 行程排序

题意

思路

代码