本文主要是介绍FZU 2227 邮票 (DFS+ 离散化 水题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem 2227 邮票
Accept: 20 Submit: 34
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem 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
21 100100 233 1100 23 2
Sample Output
1 100 21 3 2 100
Source
FOJ有奖月赛-2016年4月（校赛热身赛）题目链接：http://acm.fzu.edu.cn/problem.php?pid=2227
题目分析：题是水题，数据坑爹，离散化取入度为1的小端点搜一下即可
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int const MAX = 2e5 + 5;
map <int, int> ha, pha;
vector <int> vt[MAX];
int ans[MAX], ind[MAX], cnt, num, n;
bool vis[MAX];void DFS(int u)
{if(num == n + 1)return;int sz = vt[u].size();for(int i = 0; i < sz; i++){int v = vt[u][i];if(!vis[v]){vis[v] = true;ans[num ++] = pha[v];DFS(v);if(num == n + 1)return;}}
}int main()
{while(scanf("%d", &n) != EOF){num = 0;cnt = 0;ha.clear();pha.clear();memset(ind, 0, sizeof(ind));memset(vis, false, sizeof(vis));int u, v, tmp = 1;for(int i = 0; i < n; i++){scanf("%d %d", &u, &v);if(!ha[u]){ha[u] = tmp;pha[tmp] = u;tmp ++;}if(!ha[v]){ha[v] = tmp;pha[tmp] = v;tmp ++; }vt[ha[u]].push_back(ha[v]);vt[ha[v]].push_back(ha[u]);ind[ha[u]] ++;ind[ha[v]] ++;}int st = 0x3fffffff;for(int i = 1; i < tmp; i++)if(ind[i] == 1 && pha[i] < st)st = pha[i];ans[num ++] = st;vis[ha[st]] = true;DFS(ha[st]);for(int i = 0; i < num; i++)printf("%d%c", ans[i], i == num - 1 ? '\n' : ' ');for(int i = 0; i <= tmp; i++)vt[i].clear();}
}这篇关于FZU 2227 邮票 (DFS+ 离散化 水题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
