全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019：D - Restore the Tree

問題
解法
解答

問題

解法

問題文中に

書き足された各辺 $u \to v$ は、ある頂点 $u$ からその子孫であるような頂点 $v$ に向かって伸びています

とあるので答えは一意に定まる（これを見落としていて複数答えがあるのでないかとちょっと悩んでいた）．

ここで，書き足された辺によって根から各頂点へのパスの長さは同じか短くなるかであるから，短くなった頂点を検出し適切なその頂点の親を知りたい．

ここで，与えられたグラフは DAG であることを用いると，トポロジカルソートをすることによって根から順番に index を振りなおすことが出来る．これによって，各頂点の親として考えられる頂点（ゆえに，各頂点に入ってきている辺の出ている元）のうち，与えられたグラフで根からその頂点へのパスが最も長くなるようにしたいから，振りなおされた index の最も大きいものがその頂点の親になる．これは逆配列等のテクを使えば十分高速に処理することが出来る．O(N + M)．