693.行程排序

caution

原题链接：https://www.acwing.com/problem/content/695/

思路

先判断出起点和终点，以 “xxx - yyy 为标准，xxx 表示起点站，yyy 表示终点站。

起点的特征：只会出现在左边，并且只会出现一次

终点的特征：只会出现在右边，并且只会出现一次

途径站的特征：左右各出现一次。

找到起点和终点，结合链表的性质逐个连接起来即可。用哈希表存储起点和下一个站。遍历的时候更新起点站即可。

代码

#include <bits/stdc++.h>

using namespace std;

int T, n;

int main() {
    cin >> T;

    for (int i = 1; i <= T; i++) {
        vector<string> e, ne;
        unordered_map<string, int> l, r;
        unordered_map<string, string> link;

        cin >> n;
        while (n--) {
            string st, ed;
            cin >> st >> ed;
            e.push_back(st);
            ne.push_back(ed);
            l[st]++, r[ed]++;
            link[st] = ed;
        }

        printf("Case #%d: ", i);
        // find start and end
        string start = "", end = "";
        for (int i = 0; i < e.size(); i++) {
            if (l.count(e[i]) == 1 && r.count(e[i]) == 0) {
                start = e[i];
            }
            if (l.count(ne[i]) == 0 && r.count(ne[i]) == 1) {
                end = ne[i];
            }
        }

        for (int i = 0; i < e.size(); i++) {
            if (start == end)
                break;
            cout << start << "-" << link[start] << " ";
            start = link[start];
        }

        printf("\n");
    }
    return 0;
}