秋招每日一题T17——行程排序

题目描述

玛丽需要从某地飞往另一目的地，由于没有直达飞机，所以需要在中途转很多航班。

例如：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

思路

①想到了可能需要使用unordered_map，但看题解之前确实没想到需要使用两个unordered_map。
②开两个unordered_map，一个cnt，用于统计每个地点出现了几次，另一个为nxt，key为出发地，value为目的地。
③遍历cnt以寻找只出现一次的地名，且需要用nxt.count(i)来查看这个地名是否有目的地。如果满足条件，将这个地名作为出发地即可。
④剩下的过程则类似于链表遍历了。

代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 2e5 + 5;
int t,n;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>t;
	for(int cases = 1;cases <= t;cases ++){
		//不可能到同一中转城市两次或以上
		cin>>n;
		unordered_map<string,int> cnt;
		unordered_map<string,string> nxt;
		for(int i=1;i<=n;i++){
			string d1,d2;
			cin>>d1>>d2;
			nxt[d1] = d2;
			cnt[d1] ++, cnt[d2] ++;
		}
		string s;
		for(auto& [k,v]:cnt){
			if(v == 1 && nxt.count(k)){
				s = k;
				break;
			}
		}
		cout<<"Case #"<<cases<<": ";
		for(string i = s;nxt.count(i);i=nxt[i]){
			cout<<i<<'-'<<nxt[i]<<' ';
		}
		cout<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39