B. Queue
During the lunch break all n Berland State University students lined up in the food court. However, it turned out that the food court, too, has a lunch break
and it temporarily stopped working.
Standing in a queue that isn't being served is so boring! So, each of the students wrote down the number of the student ID of the student that stands in line directly in front of him, and the student that stands in line directly behind him. If no one stands
before or after a student (that is, he is the first one or the last one), then he writes down number 0 instead (in Berland State University student IDs are numerated
from 1).
After that, all the students went about their business. When they returned, they found out that restoring the queue is not such an easy task.
Help the students to restore the state of the queue by the numbers of the student ID's of their neighbors in the queue.
The first line contains integer n (2 ≤ n ≤ 2·105)
— the number of students in the queue.
Then n lines follow, i-th line contains the pair
of integers ai, bi (0 ≤ ai, bi ≤ 106),
where ai is
the ID number of a person in front of a student and bi is
the ID number of a person behind a student. The lines are given in the arbitrary order. Value 0 is given instead of a neighbor's ID number if the neighbor doesn't
exist.
The ID numbers of all students are distinct. It is guaranteed that the records correspond too the queue where all the students stand in some order.
Print a sequence of n integers x1, x2, ..., xn —
the sequence of ID numbers of all the students in the order they go in the queue from the first student to the last one.
4
92 31
0 7
31 0
7 141
92 7 31 141
#include<string.h>
#define count 1000005
int next[count],pre[count],c[count],vis[count],a[count],b[count];
int main()
{
int n,m,i,j,t,u;
while(scanf("%d",&n)!=EOF)
{
memset(next,-1,sizeof(next));memset(pre,-1,sizeof(pre));memset(c,0,sizeof(c));
memset(vis,0,sizeof(vis));memset(a,0,sizeof(a));memset(b,0,sizeof(b));
if(n==2){
for(i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
if(a[i]==0){
c[1]=b[i];
}
else if(b[i]==0){
c[0]=a[i];
}
}
printf("%d %d\n",c[0],c[1]);
continue;
}
for(i=1;i<=n;i++){
scanf("%d%d",&a[i],&b[i]);
next[a[i]]=b[i];
pre[b[i]]=a[i];
}
if(n%2==0){
t=1;
for(i=next[0];i!=-1 && t<n;i=next[i]){
c[t]=i;t=t+2;
}
t=n-2;
for(i=pre[0];i!=-1 && t>=0;i=pre[i]){
c[t]=i;t=t-2;
}
}
if(n%2!=0){
t=1;
for(i=next[0];i!=-1 && t<n;i=next[i]){
c[t]=i;t=t+2;vis[i]=1;
}
u=-1;
for(i=1;i<=n;i++){
if(vis[a[i]]==0 && a[i]!=0){
u=a[i];break;
}
}
while(next[u]!=-1){
u=next[u];
}
t=n-1;
for(i=u;i!=-1 && t>=0;i=pre[i]){
c[t]=i;t=t-2;
}
}
for(i=0;i<n;i++){
if(i!=n-1){
printf("%d ",c[i]);
}
else printf("%d\n",c[i]);
}
}
return 0;
}
最新文章
- TFS二次开发系列:五、工作项查询
- Linux Apache配置多个站点同时运行
- Android线程机制——AsyncTask
- linux下打开chm文件的方法
- oracle 增加字段
- 【Android - MD】之FloatingActionButton的使用
- 让 asp.net mvc 支持 带有+ _ 等特殊字符的路由
- Tencent分布式开源框架Pebble
- [CVPR2015] Is object localization for free? – Weakly-supervised learning with convolutional neural networks论文笔记
- 关于eclipse的一些问题
- 创建线程的第三种方式——使用Callable接口
- vue爬坑:把对象中的数据给了某个变量,改变一个对象的值,另一个对象也变化
- nginx负载均衡后端tomcat无法加载js资源
- 推特算法,分布式ID
- div 自适应高度
- python 基础 内置函数 和lambda表达式
- ZOJ3202-Second-price Auction(根据输入输出判断是队列还是栈)
- 关于JXL读写以及修改EXCEL文件<;转>;
- uva 1203 - Argus(优先队列)
- Apach 配置虚拟机时候DocumentRoot参数最后不要加斜杠