题目描述

有 n 辆自行车依次来到停车棚，除了第一辆自行车外，每辆自行车都会恰好停放在已经在停车棚里的某辆自行车的左边或右边。(e.g.停车棚里已经有 33 辆自行车，从左到右编号为：3,5,1。

现在编号为 22 的第 44 辆自行车要停在 5 号自行车的左边，所以现在停车棚里的自行车编号是：3,2,5,1)。给定nn辆自行车的停放情况，按顺序输出最后停车棚里的自行车编号。n\leq 100000。

输入描述

第一行一个整数 n。 第二行一个整数x。表示第一辆自行车的编号。 以下 n-1 行，每行 3 个整数 x,y,z。 z=0 时，表示编号为 x 的自行车恰停放在编号为 y 的自行车的左边。 

z=1 时，表示编号为 x 的自行车恰停放在编号为 y 的自行车的右边。

输出描述

从左到右输出停车棚里的自行车编号

输入输出样例

输入：

4
3
1 3 1
2 1 0
5 2 1

　　

　　输出:

3 2 5 1

　　

　　代码:

#include<bits/stdc++.h> //万能头文件
using namespace std;
const int n = 200010;
struct node{//双向链表
    int data;
    int preid;
    int nextid;
}nodes[n];
int now;
int locate[n];
void init(){//初始化
    nodes[0].nextid=1;
    nodes[1].preid=0;
    now=2;
}
void insert(int k,int n){//将n插到k的右边 
    nodes[now].data=n;
    locate[n]=now;
    nodes[now].nextid=nodes[k].nextid;
    nodes[now].preid=k;
    nodes[nodes[k].nextid].preid=now;
    nodes[k].nextid=now;
    now++;
}
int main(){
    int n,id,x,y,z,i;
    scanf("%d %d",&n,&id);
    init();
    insert(0, id);
    for(i=0;i<n-1;i++){
        scanf("%d %d %d",&x,&y,&z);
        if(!z){
            insert(nodes[locate[y]].preid,x);
        }else{
            insert(locate[y],x);
        } 
    }
    for (i = nodes[0].nextid; i != 1; i = nodes[i].nextid)
        printf("%d ",nodes[i].data);
}

题目链接：自行车停放 - 蓝桥云课 (lanqiao.cn)