最悪の記者(07本選4) - olpheの競プロ帖

Nチームがリーグ戦を行った。M個の勝敗の情報が与えられたとき、順位表のうちの一つを出力せよ。という問題。

なお、引き分けの試合はなく、同順位のチームもなく、順位が上のチームが下のチームに負けなかったことが保証されている。

勝ったチームから負けたチームに有向辺を張る。

以降チームは頂点とする。

全ての頂点が使われるまで、どこからも辺の伸びていない頂点を始点としBFSを行う。そのとき、通った辺は削除していく。また、訪れた頂点に伸びている辺が存在しない場合のみqueueに追加する。(そうしないと1>2,1>3,3>2のような場合にWAが発生しうる。)

また、他の順位表がありうるかどうかは、ある頂点において探索が終わったときに、queueに複数個頂点が入っていればほかの順位表がありうる。

計算量はO(max(N,M))だと思う。

難易度は7程度に感じられた。