693. Travel sequencing (map + topology)

The title is as follows

Mary needs to fly from one place to another , Because there is no direct flight , So we need to transfer many flights halfway .

for example ：SFO -> DFW DFW -> JFK JFK -> MIA MIA -> ORD.

Obviously, it is impossible to travel to the same transit city twice or more , Because it doesn't make sense .
Unfortunately , She messed up the order of her tickets , It is not easy for her to arrange the tickets according to the order of travel .
Please help Mary arrange her ticket , Arrange the tickets in the correct order .

Input format

The first line contains integers T, Expressing common ownership T Group test data .
The first row of each set of data contains an integer N.

Next 2N That's ok , Every time 2 Row group , Indicates the information of a ticket , Each line contains a string , The first line indicates the place of departure , The second row lists the destination .

Output format

Each group of data outputs a result , Each result takes up one line .
The result is expressed as Case #x: y, among x It's the group number （ from 1 Start ）,y
Is a list of tickets representing the actual trip , Each leg of the journey should be marked with source-destination Form output , The segments are separated by spaces .

Data range

1≤T≤100,1≤N≤10000

sample input ：

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

sample output ：

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

Ideas ：

map + Topology

AC The code is as follows :

#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();
}