双向链表get！

A4paper · 2018-03-27 17:32:32 · 个人记录

传送门

//感谢 夜刀神十香ღ 大佬的题解！！

int a[100010][3],n,m;
//a[i][2]表示学号为i的同学右边同学的学号
//a[i][3]表示学号为i的同学左边同学的学号

int main()
{
    cin >> n;
int j=1;
    a[1][1] = 1;
    for(int i=2;i<=n;i++)
    {
int k,p;
        cin >> k >> p;
        a[i][1] = i;
        if(p == 0)
        { 
            a[a[k][3]][2] = i;  a[i][2] = k;
            a[i][3] = a[k][3];  a[k][3] = i;
            if(k == j)  j = i;
        }
        else
        {
            a[i][2] = a[k][2];  a[a[k][2]][3]=i;
            a[k][2] = i;        a[i][3] = k;
        }
    }
    cin >> m;
    for(int i=1;i<=m;i++)
    {
        int val; cin >> val;
        if(a[val][1] != 0)
        {
            a[val][1] = 0;
            a[a[val][3]][2] = a[val][2];
            a[a[val][2]][3] = a[val][3];
            n--;
            if(val == j)    j = a[val][3];
        }
    }
    int i = 1,x = j;
    while(i <= n)
    {
        cout << a[x][1] << " ";
        x = a[x][2];
        i++;
    }
    return 0;
}