いつもは精進中になんか気づいたことがあったらTwitterでまとめちゃうんですが、この問題は結構長くなりそうなので記事にまとめることとして、書き始めたんですが、問題の制約を見落としてることにあとから気づいて、無駄記事になりました。
でもせっかく書いたので…
解説ACでした。
第一関門
グラフ中に閉路や、根の方向に戻る辺は存在しません(これにすら気づかなくて解けなかった)
これ関連の考察が個人的には最重要ポイントだったかなと思っています。
まぁ、後から読み返したら、問題文中に
書き足された各辺u→vは、ある頂点uからその子孫であるような頂点vに向かって伸びています。
って書いてあったんですけど。
閉路が存在しないのは言われてみれば簡単な話で、例えば、
こんな感じに閉路が存在したとすると、閉路を構成するどの矢印をなくしても、木が出来てしまいます。
つまり、閉路が存在すると、どこを切っても木が出来、またその木が相異なりうるということで、条件
元の木は一意に定まる。
を満たさなくなってしまいます。
戻る辺に関しては一般的な図を書くのは難しいので書きませんが、この場合も2通り以上の木が出来てしまうので、戻る辺を書き足すことも出来ません。
これに気づけば後の発想は比較的楽で、根に入っていく方向の矢印が書き足されていることは有りません(書き足されているとそこに閉路が必ず出来てしまいます)。
つまり、入字数0のノードを見つけたら、根と考えることができます。
根が見つかった後。
こんな感じのものを元に考えます
さて、適当に辺を足してみます。
たされる辺は制約上、所謂近道になるので、近道が出てきたらそれを無視してけばいいですね。
この近道を無視するというのが、結構厄介です。というのも
- 何も考えずにBFSすると複数回頂点を訪れるのを排除できない関係上、深い探索を繰り返してTLEする。
- 訪れた頂点を即pushしてしまうと、書き足された頂点による近道で、本来求めたいグラフでの距離よりも早く頂点がpushされてしまう(すると、この子孫達の順番も変わってぐちゃぐちゃになる)
ということで、以下の方針で実装したらなんか通りました。
- 基本はBFS
- 入次数をどうせ数えてあるので、それを使い果たすまでpushしない(つまり最後に訪れる≒近道していないタイミングまでまつ)
トポロジカルソートの方の解説はよくわかっていませんが、解けたので、ヨシ!(良くない)
おわりに
制約はちゃんと読もう！