题意：
有n辆车和q次操作，每次操作有三种类型：
1 , x , y表示将y连到x的后面
2 , x , y表示将y从x后面断开
3 , x表示询问x相连的车的集合。
思路：
实质上是双向链表的操作，想着用去掉路径压缩的并查集应该也可以实现。
l i表示i前面的车是谁，r i表示后面的车是谁。
对于前两种操作都只需要修改x , y的l , r数组。
对于第三种操作，先找到x所在集合最左边的端点，然后一直向右遍历，直到r y = = y，说明后面没有后续节点了。
代码：
// Problem: D - Play Train // Contest: AtCoder - UNICORN Programming Contest 2021(AtCoder Beginner Contest 225) // URL: https://atcoder.jp/contests/abc225/tasks/abc225_d // Memory Limit: 1024 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=4e5+7,maxm=1e6+7,mod=1e9+7; int l[maxn],r[maxn]; int Find(int x){ if(x!=l[x]) return Find(l[x]); return x; } void Union(int x,int y){ r[x]=y;l[y]=x; } void Del(int x,int y){ r[x]=x;l[y]=y; } void output(int x){ vector<int>g; int y=Find(x); while(r[y]!=y){ g.push_back(y); y=r[y]; } g.push_back(y); cout<<g.size()<<" "; for(auto tt:g) cout<<tt<<" "; puts(""); } int main(){ int n=read,q=read; for(int i=1;i<=n;i++) l[i]=i,r[i]=i; while(q--){ int op=read; if(op==1){ int x=read,y=read; Union(x,y); } else if(op==2){ int x=read,y=read; Del(x,y); } else{ int x=read; output(x); } } return 0; }
