AtCoder Beginner Contest 225 D - Play Train

問題の要約
　電車がN個あり,電車1,電車2,...,電車Nと名前がついている。
　はじめ電車どうしは連結しておらず,バラバラ。
　クエリがQ個与えられるので,与えられた順番に処理しなさい。
　クエリは次の3種類のいずれか。
　・1 x y:電車xの後部と,電車yの前部を連結させる。
　　以下のことが保証されている。
　　・x≠y
　　・クエリを処理する直前に,電車xの後部と連結している電車は存在しない。
　　・クエリを処理する直前に,電車yの前部と連結している電車は存在しない。
　　・クエリを処理する直前に,電車xと電車yは異なる連結成分に属する。
　・2 x y:電車xの後部と,電車yの前部を分離させる。
　　次のことが保証されている。
　　・x≠y
　　・クエリを処理する直前に,電車xの後部と電車yの前部は直接連結している。
　・3 x:電車xが含まれる連結成分に属する電車の番号を,先頭から順番に全て出力する。
制約　
　2<=N<=10^5
　1<=Q<=10^5
　1<=x<=N
　1<=y<=N

入力
　N Q
　query1
　query1
　.
　.
　.
　queryQ

考え方
　1,クエリを1から順番に取り込み1,2,3で条件分岐する。
　2,データ構造にvector<vector<long long>>Trainsを使う。
　3,初期状態として1,2,...,Nのそれぞれに1,2,...,Nの電車を配置しておく。
　4,クエリが1 x yのとき。
　　全ての電車を探索して電車xを探し,その後部にyの場所にある電車を全て連結する。
　　yの場所の電車を全てなくす。
　5,クエリが2 x yのとき。
　　全ての電車を探索して電車xを探し,その後ろ全ての電車を順番を変えずyの場所に置く。
　　電車xの後ろの電車を全てなくす。
　6,クエリが3 xのとき。
　　
　　全ての電車を探索して電車xを探し,電車xが連結している連結成分の数を出力し,その一番前から一番後ろの電車を全て出力していく。
　7,結果TLE。
#include<iostream>
#include<vector>

using namespace std;

int main(){
  long long N,Q;
  cin >> N >> Q;
  
  vector<vector<long long>> Trains(N+1);
  for(long long i = 1; i <= N; i++){
    Trains[i].push_back(i);
  }
  
  for(long long q = 0; q < Q; q++){
    long long query;
    long long x,y;
    bool check = false;
    cin >> query;
    if(query == 1){
      cin >> x >> y;
      for(long long i = 1; i <= N; i++){
        for(long long j = 0; j < (long long)Trains[i].size(); j++){
          if(Trains[i][j] == x){
            for(long long k = 0; k < (long long)Trains[y].size(); k++){
              Trains[i].push_back(Trains[y][k]);
            }
            Trains[y].clear();
            check = true;
          }
          if(check){break;}
        }
        if(check){break;}
      }
    }else if(query == 2){
      cin >> x >> y;
      for(long long i = 1; i <= N; i++){
        for(long long j = 0; j < (long long)Trains[i].size(); j++){
          if(Trains[i][j] == x){
            for(long long k = j+1; k < (long long)Trains[i].size(); k++){
              Trains[y].push_back(Trains[i][k]);
            }
            Trains[i].erase(Trains[i].begin()+j+1, Trains[i].end());
            check = true;
          }
          if(check){break;}
        }
        if(check){break;}
      }
    }else if(query == 3){
      cin >> x;
      for(long long i = 1; i <= N; i++){
        for(long long j = 0; j < (long long)Trains[i].size(); j++){
          if(Trains[i][j] == x){
            cout << Trains[i].size() << " ";
            for(long long k = 0; k < (long long)Trains[i].size(); k++){
              cout << Trains[i][k] << " ";
            }cout << endl;
            check = true;
          }
          if(check){break;}
        }
        if(check){break;}
      }
    }
  }
  
  return 0;
}
　8,もう少し考えてみる。
　　時間がかかっているのは,xを見つけるところと連結と分離の操作。
　　ある電車iの前部と後部だけを記憶するようにしてみる。
　　vector<long long> front;
　　vector<long long> rear;
　9,クエリが1 x yのとき。
　　rearのxにyを代入。
　　frontのyにxを代入。
　10,クエリが2 x yのとき。
　　rearのxにnullを代入。
　　frontのyにnullを代入。
　11,クエリが3 xのとき。
　　frontのxをnullになるまでたどる。その電車をfとffとする。
　　fからrearをnullまでたどりcountに1を足していく。
　　ffからrearをnullまでたどりながら電車の番号を出力していく。

実際のプログラム
#include<iostream>
#include<vector>

using namespace std;

const long long null = -1;

int main(){
  long long N,Q;
  cin >> N >> Q;
  
  vector<long long> front(N+1, null);
  vector<long long> rear(N+1, null);
  
  for(long long q = 0; q < Q; q++){
    long long query;
    long long x,y;
    cin >> query;
    if(query == 1){
      cin >> x >> y;
      rear[x] = y;
      front[y] = x;
    }else if(query == 2){
      cin >> x >> y;
      rear[x] = null;
      front[y] = null;
    }else if(query == 3){
      cin >> x;
      long long f;
      long long ff;
      do{
          f = x;
        ff = x;
        x = front[x];
      }while(x != null);
      long long count = 0;
      do{
          count++;
        f = rear[f];
      }while(f != null);
      cout << count << " ";
      do{
        cout << ff << " ";
        ff = rear[ff];
      }while(ff != null);
      cout << endl;
    }
  }
  
  return 0;
}