全国統一プログラミング王 D Restore the Tree

D

所感

有向辺を大小関係と見る + トポロジカルソートという単語 まで出てきて解けないのは怠慢すぎる、猛省

問題概要

N頂点の根つき木に、祖先->子孫であるようなM本の有向辺を追加したグラフが与えられます。元のグラフを復元してください。

取った方針

有向辺を大小関係と見た時にソートしたものが得られればよいことがわかる。グラフにおけるノードのソートを行うアルゴリズムがあったことを思い出す。wikipediaを見たらなんとなく難しそうだったので閉じてそのまま迷走して終了(は？)

正しい方針

トポロジカルソートはグラフにおいて辺を大小関係と見た時に小さい順に並べ替えるアルゴリズムである。
これをしたあとに、自分の親候補のうちトポロジカルソートにおいて一番順番が大きいものを親として選べば解が得られる。
理由: ノードuの親候補のうち最も大きくないノードv2を選んだ場合、親候補でより大きいノードv1が存在することになる。
v1は親候補なので入力にはv1->uなるエッジがあるはずだが、ノードuの親候補のうち最も大きくないノードv2を選んだ場合のグラフではuとv1に子孫関係はないはずであり、題意に矛盾。

得られた知見

・トポロジカルソートはグラフにおいて辺を大小関係と見た時に小さい順に並べ替えるアルゴリズムである。
・500は解ける
・500は解ける
・500は解ける
・500は解ける

解くのに必要な要素

・トポロジカルソート

周辺調査によって得られた知見

特になし