用一个哈希表把每张机票的出发地和目的地都存起来, 就得到了类似于链表的一个东西, 这时候我们只需要找的整个行程最开始出发的地方, 遍历即可。
//
// Created by trudbot on 2022/6/26.
//
#include <bits/stdc++.h>
using namespace std;
unordered_map<string, string> nextCity;
unordered_map<string, bool> selected;
int main() {
int T, N;
cin >> T;
string s1, s2;
for(int i=1; i<=T; i++)
{
cin>> N;
getchar();
for(int j=0; j<N; j++)
{
getline(cin, s1);
getline(cin, s2);
nextCity[s1] = s2;
selected[s2] = true;
}
string curr;
for(auto &city : nextCity)
{
if(selected.count(city.first) == 0)
{
curr = city.first;
break;
}
}
printf("Case #%d:", i);
while(nextCity.count(curr) != 0)
{
cout << " " << curr << "-" << nextCity[curr];
curr = nextCity[curr];
}
printf("\n");
nextCity.clear();
selected.clear();
}
return 0;
}