input:hotel.in output:hotel.out

时间限制: 1000 ms 空间限制: 262144 KB

题目描述

一共有N个人在排队，他们都有自己的编号，保证编号大于0且小于2000001，
每个人都有自己前面和后面人的编号，如果他前面或后面没人，则会用 0 代替，
一共只有一条拿酒的队伍。

输入

第一行一个整数 N 表示人的个数
接下来 N 行表示每个人记下的编号
保证每个人的标号不同

输出

一行 N 个数，中间用空格隔开，表示这个编号。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
【样例输入 1】
4
92 31
0 7
31 0
7 141
【样例输入 2】
5
0 1
1 4
4 0
3 2
5 3

样例输出

1
2
3
4
【样例输出 1】
92 7 31 141
【样例输出 2】
5 1 3 4 2

数据范围限制

代码

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
40
41
42
#include<bits/stdc++.h>
using namespace std;
const int maxn=2100000;
bool sf[maxn];
int n,x,y,a[maxn],all,next[maxn],last[maxn],first1,first2;
int main()
{
    freopen("hotel.in","r",stdin);
    freopen("hotel.out","w",stdout);
    sf[0]=1;
    memset(last,-1,sizeof(last));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        next[x]=y;
        last[y]=x;
        if(x==0)
            first2=y;
        if(sf[x]==0)
        {
            a[++all]=x;
            sf[x]=1;
        }
        if(sf[y]==0)
        {
            a[++all]=y;
            sf[y]=1;
        }
    }
    for(int i=1;i<=all;i++)
        if(last[a[i]]==-1)
            first1=a[i];
    for(int i=1;i<=n/2;i++)
    {
        cout<<first1<<" "<<first2<<" ";
        first1=next[first1];
        first2=next[first2];
    }
    if(n%2==1) cout<<first1;
    return 0;
}