Official

D - Takahashi Tour Editorial by kyopro_friends


都市を頂点、道路を辺としたグラフは、制約から木であることがわかります。高橋くんの旅は木のDFSにほかなりません。

都市に出入りしたタイミングでそのことを記録するようなDFSを行うことでこの問題を解くことが出来ました。

実装例(C++)
実装例(Python)

なお、今回の問題で答えた頂点の番号の列は、木のオイラーツアー(Euler Tour)と呼ばれ、木に関するさまざまな問題を解く際に利用されます。

posted:
last update: