AtCoder-ABC213 D - Takahashi Tour【Python解答例】

AtCoder Beginner Contest213のD問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 213 - AtCoder

AtCoder Beginner Contest213 D - Takahashi Tour

D - Takahashi Tour

問題文

AtCoder 国には 1 から N の番号がついた N 個の都市と、1 から N−1 の番号がついた N−1 個の道路があります。
道路 i を通ると都市 Ai と都市 Bi の間を相互に移動することができます。全ての都市は道路を使って互いに行き来できることが保証されます。

高橋くんは都市 1 を出発し、次のルールで旅をします。

・いまいる都市と道路で直接つながっている都市のうち、まだ訪れたことがない都市が存在するとき、そのような都市のうち番号が最も小さい都市へ移動する
・そのような都市が存在しないとき
いまいる都市が都市 1 なら旅を終了する
そうでないなら、いまいる都市を初めて訪れたときに直前にいた都市へ移動する
高橋くんが旅の過程で訪れる都市を順に答えてください。

制約

・2 ≤ N ≤ 2×10^5
・1 ≤ Ai,Bi ≤ N
・全ての都市は道路を使って互いに行き来できる

解答例

import sys
sys.setrecursionlimit(10**7) #再帰回数の上限変更

n = int(input())

graph = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(n+1):
    graph[i].sort()

ans = []
def dfs(x,y):
    ans.append(x)
    for next in graph[x]:
        if next != y:
            dfs(next, x)
            ans.append(x)

dfs(1, 0)
print(*ans)

解説

高橋君がたどる都市を順番に答える問題で、オイラーツアーという問題と同じのようです。

DFSするために隣接グラフgraphを持ち、さらに小さい都市から移動するのでgraph[i]をソートします。

DFSは現在の都市xと移動前の都市yを引数として、ソートしたgraph[x]の順番で移動していきました。
移動できる都市があれば次の都市next、および移動前の都市番号として現在の都市番号を渡していきます。
移動できる都市がなくなれば元の都市に戻ります。
移動した都市は順次 ans配列に格納していきました。

DFSが終わったあとにansをアンパックして出力すればACでした。

ABC213の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com