ABC225 D問題[双方向連結リスト][リストのアンパック]

D - Play Train

■要約

　実際に参戦中，なんとなく貪欲に探索すればできそうな気がしたが，実装に至らず．

【AtCoder解説】PythonでABC225のA,B,C,D問題を制する！ - Qiita

上のサイトを参考にさせていただくと，どうやら，双方向連結リストというデータ構造を使えば上手く行ったみたいだ．これは特に難しいことではなく，各番号の前と後ろに何の番号が繋がっているかを保存しておけば良いというものだ．これを使えば，簡単に電車の前後ろに連結しているものだけを保存しておけるので，いちいち今電車がどうなっているかを考えずに済む．

また意識しておくこととして，今回は出力が最大10**6個以下である点だ．これにより制限時間以内に間に合う．

頑張ればACできそうだっただけに悔しい

n,Q = map(int, input().split())
_next = [-1]*(n+1)
_prev = [-1]*(n+1)

for _ in range(Q):
 query = list(map(int, input().split()))
 q = query[0]
 #電車xの後部と電車y部の前部を連結させる
 if q == 1:
   x,y = query[1:]
   _next[x] = y
   _prev[y] = x
 #電車xの後部と電車y部の前部を連結させる
 elif q ==2:
   x,y = query[1:]
   _next[x] = -1
   _prev[y] = -1
 #電車xが含まれる連結部分を，先頭から順番に出力
 else:
   x = query[1]
   ans = []
   
   curr = x
   #電車を先頭までたどる
   while _prev[curr] != -1:
     curr = _prev[curr]
     
   #先頭から後部までたどる
   while curr != -1:
     ans.append(curr)
     curr = _next[curr]
     
   print(len(ans), *ans)