AOJ 0519 : Worst Sportswriter
問題
Worst Sportswriter | Aizu Online Judge
解法
aがbに勝ったという情報に対して、順位が a < b となることが保証されている。
入力が順序集合を表すと解釈できるため aがbに勝つならば、
aからbに有向辺を張りグラフを構築し、トポロジカルソートを行えばよい事が分かる。
例として、以下の入力に対するグラフを示す。
1 2 3 1 3 2 3 4 4 1
順位の候補が複数あるか という判定は、トポロジカルソートを行う過程で
頂点を削除した際に入次数=0となる頂点が同時に複数個登場するか という点で判断した。
また、題意よりグラフに閉路がないことは保証されている。
