AcWing 693. 行程排序
原题链接
简单
作者:
曦薇
,
2022-06-27 10:20:18
,
所有人可见
,
阅读 155
思路
- 入度为 $0$ (即没有航班抵达的地方是出发点),然后从出发点开始遍历航班即可找到完整路线。
- 时间复杂度为 $O(T \times N)$ ,空间复杂度为 $O(N)$ 。
AC代码
#include<bits/stdc++.h>
using namespace std;
int main(void){
int num,n,i,j;
scanf("%d",&num);
for(j=1;j<=num;j++){
unordered_set<string> place;
unordered_set<string> arrive;
unordered_map<string,string> ap;
scanf("%d",&n);
string s,t;
for(i=1;i<=n;i++){
cin>>s>>t;
place.insert(s),place.insert(t);
arrive.insert(t);
ap[s]=t;
}
string tmp;
unordered_set<string>::iterator it;
for(it=place.begin();it!=place.end();it++){
if(arrive.count(*it)==0){
tmp=(*it);
}
}
printf("Case #%d:",j);
for(i=1;i<=n;i++){
cout<<" "<<tmp<<"-"<<ap[tmp];
tmp=ap[tmp];
}
cout<<endl;
}
return 0;
}