693. 行程排序(map + 拓扑)

题目如下

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

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

显然旅途中不可能到同一中转城市两次或以上，因为这没有意义。
不幸的是，她将自己的机票的顺序搞乱了，将机票按乘坐顺序整理好对她来说不是一件容易的事。
请你帮助玛丽整理机票，使机票按正确顺序排列。

输入格式

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

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

输出格式

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

数据范围

1≤T≤100,1≤N≤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

思路：

map + 拓扑

AC代码如下:

#include <bits/stdc++.h>
#define buff \ ios::sync_with_stdio(false); \ cin.tie(0);
//#define int long long
using namespace std;
const int N = 10009;
int d[N];
int n;
map<string, int> mp;
int h[N], e[N], ne[N], idx;
int cnt;
string ch[N];
int rou;
void add(int a, int b)
{
    
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void topsort()
{
    
    int q[N];
    int tt = -1, hh = 0;

    for (int i = 1; i <= cnt; i++)
        if (!d[i])
        {
    
            q[++tt] = i;
            break;
        }
    while (hh <= tt)
    {
    
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i])
        {
    
            int j = e[i];
            d[j]--;
            if (!d[j])
                q[++tt] = j;
        }
    }
    for (int i = 0; i < cnt - 1; i++)
        cout << ch[q[i]] << '-' << ch[q[i + 1]] << ' ';
}

void solve()
{
    
    rou++;
    mp.clear();
    memset(d, 0, sizeof d);
    memset(h, -1, sizeof h);
    cnt = 0, idx = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
    
        string a, b;
        cin >> a >> b;
        if (!mp[a])
        {
    
            mp[a] = ++cnt;
            ch[cnt] = a;
        }
        if (!mp[b])
        {
    
            mp[b] = ++cnt;
            ch[cnt] = b;
        }
        d[mp[b]]++;
        add(mp[a], mp[b]);
    }

    cout << "Case #" << rou << ": ";
    topsort();
    cout << '\n';
}
int main()
{
    
    int t;
    cin >> t;
    while (t--)
        solve();
}