AOJ1236 Map of Ninja House

問題文が長いので, 概要だけ説明すると, 深さとある頂点の辺の数が与えられるので, ここからグラフを復元する問題

解法
まず頂点数は正の数の総数であることが分かる.
すなわち, i番目のデータをみて, それが正ならば頂点番号を振り分ける.
逆に負であればその先に頂点は存在しないので, 巻き戻すみたいな処理が必要になる.

stackに頂点番号, 始点からの距離を持たせて, データが正であれば, その先頭と新しい頂点番号を辺でつなぐ.
データが負であれば, v[i] == dist[to] - dを満たすtoを探してtoとstackの先頭の頂点番号を辺でつなぐ.

データの読み取り後にドアの数がすべて見つかった頂点を先頭から除くことで巻き戻しの操作も可能なのでグラフを復元できる.

h3mky0's blog