Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://codeforces.com/contest/29/problem/C 题意：给出n个边的关系，保证可以构成一条链。正向或者反向输出这个链。 思路：由于下标很大(1E9)，而关系个数只有1E5..需要离散化。。而且离散化的同时不能丢失边的关系。。。实际上。。直接用vector+map就好了。。。 map >e;即可。然后找到一个度为1的点。。做个dfs…
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月30日 星期三 19时55分15秒
4File Name :code/cf/problem/29C.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34map<int,vector<int> >e;
35map<int,bool>vis;
36map<int,int>in;
37map<int,int>::iterator it;
38int beg;
39int n ;
40void dfs( int x)
41{
42 vis[x] = true;
43 printf("%d ",x);
44 for ( int i = 0 ; i < e[x].size() ; i++ )
45 {
46 int v = e[x][i];
47 if (!vis[v]) dfs(v);
48 }
49}
50int main()
51{
52 #ifndef ONLINE_JUDGE
53 freopen("code/in.txt","r",stdin);
54 #endif
55
56 cin>>n;
57 vis.clear();
58 in.clear();
59
60
61 for ( int i = 1 ; i <= n ; i++)
62 {
63 int u,v;
64 scanf("%d %d",&u,&v);
65 e[u].push_back(v);
66 e[v].push_back(u);
67 in[u]++;
68 in[v]++;
69 }
70
71 for ( it=in.begin() ;it!=in.end();it++)
72 {
73 if (it->second ==1)
74 {
75 beg = it->first;
76 break;
77 }
78 }
79 dfs(beg);
80
81 #ifndef ONLINE_JUDGE
82 fclose(stdin);
83 #endif
84 return 0;
85}