玛丽需要从某地飞往另一目的地,由于没有直达飞机,所以需要在中途转很多航班。
显然旅途中不可能到同一中转城市两次或以上,因为这没有意义。
不幸的是,她将自己的机票的顺序搞乱了,将机票按乘坐顺序整理好对她来说不是一件容易的事。
请你帮助玛丽整理机票,使机票按正确顺序排列。
第一行包含整数 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
#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();
}