链表小题.Play Train AtCoder - abc225_d

链接

由于是7个月前的代码，可能不是最优解或者可能冗余，但必定正确

Takahashi is playing with toy trains, connecting and disconnecting them.
There are N toy train cars, with car numbers: Car 1, Car 2, \ldots…, Car N.
Initially, all cars are separated.

You will be given Q queries.

Process them in the order they are given.

There are three kinds of queries, as follows.

• 1 x y: Connect the front of Car y to the rear of Car x.
  It is guaranteed that:

  • x \neq yx=y
  • just before this query, no train is connected to the rear of Car x;
  • just before this query, no train is connected to the front of Car y;
  • just before this query, Car x and Car y belong to different connected components.

• 2 x y: Disconnect the front of Car y from the rear of Car x.
  It is guaranteed that:

  • x \neq yx=y;
  • just before this query, the front of Car y is directly connected to the rear of Car x.

• 3 x: Print the car numbers of the cars belonging to the connected component containing Car x, from front to back.

题目大意

有n辆车和q次操作，每次操作有三种类型：
1,x,y 表示将y yy连到x xx的后面
2,x,y表示将y yy从x xx后面断开
3,x表示询问x xx相连的车的集合

#include
using namespace std;
int n,q,i,j,k,t,x,y,z;
int l[199999],r[199999];
vector<int>::iterator it;
int main(){
   cin>>n>>q;
   while(q--){
   		cin>>z>>x;
   		if(z!=3){
   			cin>>y;
		}
		if(z==1){
			l[y]=x;
			r[x]=y;
		}
		else if(z==2){
			l[y]=0;
			r[x]=0;
		}
		else{
			vector<int>s;
			y=r[x];
			while(x){
				s.push_back(x);
				x=l[x];
			}
			reverse(s.begin(),s.end());
			while(y){
				s.push_back(y);
				y=r[y];
			}
			cout<size();
			for(it=s.begin();it!=s.end();++it){
				cout<<" "<<*it;
			}
			cout<
		}
   }
    return 0;
}