STL(list)(双向链表）

参考博客

#include<bits/stdc++.h>
using namespace std;
int n,m;
int const N=1e5+7;
list<int>s;
list<int>::iterator pos[N];   //用find会超时，所以用数组记录位置 
int vis[N];
int main(){
    cin >> n;
    s.push_back(1);
    pos[1]=s.begin();
    for(int i=2;i<=n;++i){
        int k,p;
        cin >> k >> p;
        if(p==0){
            pos[i]=s.insert(pos[k],i);   //list<int>::iterator it=find(s.begin(),s.end(),k);
        }
        else{
            list<int>::iterator it=pos[k];
            it++;
            pos[i]=s.insert(it,i);
        }
    }
    cin >> m;
    while(m--){
        int x;
        cin >> x;
        if(vis[x]==0)
          s.erase(pos[x]);   //删除位置为pos[x]上的元素
          vis[x]=1;
    }
    for(list<int>::iterator it=s.begin();it!=s.end();++it){
        cout << *it << " ";
    }
    return 0;
}