AcWing 693. 行程排序--找到度为1的根节点
原题链接
简单
作者:
追梦少年_ML
,
2022-07-06 12:29:45
,
所有人可见
,
阅读 127
#include<bits/stdc++.h>
using namespace std;
int main(){
int i,t,n;
cin>>t;
for(int k=1;k<=t;k++){
cin>>n;
map<string,int> mp; //存储地方出现的次数
vector<vector<string> > ve;
map<string,int> mp1; //存储地方出现的顺序
string from,to;
for(i=1;i<=n;i++){
cin>>from>>to;
mp[from]++;
mp[to]++;
mp1[from]=i;
ve.push_back({from,to});
}
for(i=0;i<n;i++){
if(mp[ve[i][0]]==1) break;
}
string start=ve[i][0];
cout<<"Case #"<<k<<": ";
i=0;
while(i<n){
cout<<start<<"-"<<ve[mp1[start]-1][1]<<" ";
start=ve[mp1[start]-1][1];
i++;
}
cout<<endl;
}
return 0;
}