题目描述
玛丽需要从某地飞往另一目的地,由于没有直达飞机,所以需要在中途转很多航班。
例如:SFO -> DFW DFW -> JFK JFK -> MIA MIA -> ORD。
显然旅途中不可能到同一中转城市两次或以上,因为这没有意义。
不幸的是,她将自己的机票的顺序搞乱了,将机票按乘坐顺序整理好对她来说不是一件容易的事。
请你帮助玛丽整理机票,使机票按正确顺序排列。
输入格式
第一行包含整数 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
算法1
(暴力枚举) $O(n^2)$
咋一看是单链表,处理下数据顺序即可
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int t,n;
int main()
{
cin>>t;
for (int i = 1; i <= t; i ++ )
{
map<string,string>ne,e;
cin>>n;
string a,b;
for (int j = 0; j < n; j ++ )
{
cin>>a>>b;
ne[a]=b;
e[b]=a;
}
string start;//起始起点
while(e[a]!="")a=e[a];
start = a;
cout<<"Case #"<<i<<":";
for(string i = start;ne[i]!="";i = ne[i])
cout<<" "<<i<<"-"<<ne[i];
cout<<'\n';
}
return 0;
}