AcWing 5133. 奶牛排队
原题链接
困难
作者:
文采飞杨的小皓
,
2023-08-05 22:31:59
,
所有人可见
,
阅读 95
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
const int N = 1e6+10,INF = 1e6+11;
int pre[N],ne[N],jud[N];
int n;
vector<int> Pre,Ne;
int main()
{
cin>>n;
for(int i=0;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
if(a == 0) a = INF;
if(b == 0) b = INF;
jud[a]++;jud[b]++;
pre[b] = a;
ne[a] = b;
}
int t = INF;
while(ne[t] != 0&&ne[t] != INF){
Ne.push_back(ne[t]);
t = ne[t];
}
int t1 = 0,t2 = 0;
if(ne[t] == INF){
int cnt = 0;
for(int i=1;i<=N;i++){
if(jud[i] == 1){
cnt++;
if(cnt == 1)t1 = i;
else{
t2 = i;
break;
}
}
}
if(ne[t1] == 0) t = t1;
else t = t2;
}else t = INF;
if(t != INF) Pre.push_back(t);
while(pre[t] != 0){
Pre.push_back(pre[t]);
t = pre[t];
}
reverse(Pre.begin(),Pre.end());
int i = 0;
while(1){
if(i<Pre.size()) printf("%d ",Pre[i]);
if(i<Ne.size()) printf("%d ",Ne[i]);
else break;
i++;
}
return 0;
}