官方题解

题目大意

起初，数字 $1\sim n$ 之间相互独立，给出 $q$ 次查询，每次查询为以下三种的一种：

• 将两个没有连接起来的数字按顺序前后连接起来；
• 将两个已经连接起来的数字分开；
• 输出某一个数字所有链上从头到尾所有的数字以及个数。

解题思路

由于要涉及到按顺序连接和断开的操作，不难想到我们可以通过使用数组模拟链表的方式进行这一系列操作。

$l_i$ ：表示 $i$ 这个数字左边的数字是多少，如果没有则为 $0$ 。

$r_i$ ：表示 $i$ 这个数字右边的数字是多少，如果没有则为 $0$ 。

于是，对于第一种操作 1 x y ，我们可以用以下代码完成：

r[x]=y;
l[y]=x;

注意这里是有顺序的，所以 $x$ 和 $y$ 的顺序不能反。

对于第二种操作 2 x y ，我们可以用以下代码完成：

r[x]=l[y]=0;

对于第三种操作，我们可以直接先暴力找到 $x$ 所在链的最左侧点，然后再依次向后遍历，存储所有的数，最后输出其个数以及所有数字即可。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int l[N],r[N];
int ans[N];
int idx;

int main(){
    int n,q;cin>>n>>q;
    while(q--){
        int op;cin>>op;
        if(op==1){
            int x,y;cin>>x>>y;
            r[x]=y;
            l[y]=x;
        }
        else if(op==2){
            int x,y;cin>>x>>y;
            r[x]=0;
            l[y]=0;
        }
        else{
            int x;cin>>x;
            int rt=x;
            while(l[rt]) rt=l[rt];

            idx=0;
            while(rt){
                ans[++idx]=rt;
                rt=r[rt];
            }
            cout<<idx<<" ";
            for(int i=1;i<=idx;i++) cout<<ans[i]<<" ";
            cout<<endl;
        }
    }
    return 0;
}