ABC213 D Takahashi Tour
$ A_i
と
$ B_i
を結んだグラフを考える. ここで, あらかじめ各頂点
$ i
について, 隣接リストの頂点を昇順にソートしておく. すると, 求める都市の順序はオイラーツアーそのものであり, これはDFSをすることで求められる.
よってこの問題を
$ O(N \log N)
で解くことができた.
実装例:
https://atcoder.jp/contests/abc213/submissions/24866136