本文共 1487 字，大约阅读时间需要 4 分钟。
【FZU 2227 --- 邮票】DFS+离散化
Description 一天Bob收到一封信。Bob知道瓦罗兰大陆的邮局从A城市送信到B城市，乐意使用从A城市到B城市的邮票（A, B）,或者使用从B城市到A城市的邮票（A, B），但是由于瓦罗兰大陆的城市繁多，所以并不是所有城市之间都能直接发送接收信件，换句话说，某两个城市想要通行邮件必须经过其他城市才行，但是邮局发送一次邮件的路途中从不会通过一座城市两次。
现在在Bob的信封上有N个邮票，Bob想知道这封信件是如何周转到达他手中的。
Input
题目有多组数据。
每组数据第一行包含一个整数，N ( 2 <= N <= 1e5)，代表信件上的N封邮票。
接下有N行数据。第 i 行数据包含两个整数 ui，vi，代表从城市ui发送到城市vi的邮票，ui代表城市的编号，每个城市的编号互不相同，(ui != vi ，1 <= ui, vi <= 1e9)。
输入数据保证有解。
Output
每组样例的结果输出为一行， 每行包括N+1个被空格隔开的整数，代表着信件依次经过的城市编号。
若有多组可行答案，输出字典序最小的那组答案。
Sample Input
2
1 100
100 2
3
3 1
100 2
3 2
Sample Output
1 100 2
1 3 2 100
解题思路：
读题后很容易想到DFS，但是数据量过大（1e9），数组存不下这么大的数据，所以我们先离散化，然后找个起点直接DFS就行。
AC代码：
#include #include #include
转载地址：http://oiyof.baihongyu.com/