模拟图链
$O(n)$
解题步骤:
- 将所有航班的入读和出度存储,然后找出头和尾
- 在输入的同时,存储所有航班中起点的位置
- 最后按照链的顺序输出
问题迎刃而解。
AC code
#include<iostream>
#include<cstring>
#include<map>
#define s first
#define e second
using namespace std;
const int N=10010;
string ft[N][2];
int main()
{
int T; cin>>T;
for(int ith=1;ith<=T;ith++)
{
int n; cin>>n;
map<string,int> din,dout,sf; //记录入度,出度和下一班的位置
for(int i=0;i<n;i++)
{
cin>>ft[i][0]>>ft[i][1];
din[ft[i][1]]++,dout[ft[i][0]]++;
sf[ft[i][0]]=i;
//cout<<ft[i][0]<<' '<<ft[i][1]<<endl;
}
int start,end;
for(int i=0;i<n;i++) //寻找起点
if(!din.count(ft[i][0])) start=i;
for(int i=0;i<n;i++) //寻找终点
if(!dout.count(ft[i][1])) end=i;
printf("Case #%d:",ith);
for(int i=start;;i=sf[ft[i][1]])
{
cout<<' '<<ft[i][0]<<'-'<<ft[i][1];
if(i==end) break;
}
cout<<endl;
}
return 0;
}