Official
D - Takahashi Tour Editorial by kyopro_friends
都市を頂点、道路を辺としたグラフは、制約から木であることがわかります。高橋くんの旅は木のDFSにほかなりません。
都市に出入りしたタイミングでそのことを記録するようなDFSを行うことでこの問題を解くことが出来ました。
なお、今回の問題で答えた頂点の番号の列は、木のオイラーツアー(Euler Tour)と呼ばれ、木に関するさまざまな問題を解く際に利用されます。
posted:
last update: