双链表 40分求助 #234wa了
查看原帖
双链表 40分求助 #234wa了
417398
xiangnan楼主2021/10/18 15:01

以下是原始代码 请大佬帮忙看下有什么不对 感谢

#include<iostream>
using namespace std;
const int N=1e6+10;
int e[N],l[N],r[N],idx,ch[N];//e存储第几个同学 l[]该点左侧下标 r[]右侧下标 
                             //idx表示插入点下标 ch表示通过第几个同学找到该同学的下标
int n,m;
void init()  //双链表初始化 在-1 0 之间插入 同时0是结束标志 
{ 
    l[0]=-1,r[-1]=0;
    idx=1;
}

void insert(int k,int x)  //在第k个点右边插入x
{
    ch[x]=idx;        //记录x的下标
    e[idx]=x;        //记录该下标时的第几个同学
    /*
    以下是双链表插入操作
    */
    r[idx]=r[k];
    l[idx]=k;
   
    l[r[k]]=idx;
    r[k]=idx;
    idx++;
}

void remove(int k)//删除第k个下标 
{
   r[l[k]]=r[k];
   l[r[k]]=l[k];
    
}
int main()
{
    cin>>n;
    init();
    insert(-1,1);  
    for(int i=2;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        if(y==1)    insert(ch[x],i);   //ch是将输入的哪位同学转化成下标操作
        else       insert(l[ch[x]],i);//去过Y==0则转化成在该点的左边点的右边插入
    }

     cin>>m;
     while(m--)
     {
         int k;
         cin>>k;
         remove(ch[k]);
     }
    
       int pos=r[-1];   //遍历输出
     while(pos!=0)
     {
         cout<<e[pos]<<" ";
         pos=r[pos];
     }
}
2021/10/18 15:01
加载中...