AtCoder Beginner Contest 139 E: League 解説の解説

方針は2つあり，貪欲法とトポロジカルソートを利用するものがある．

貪欲法

問題より，各人には次に対戦すべき相手リストLが与えられる． Aさんの次に対戦すべき人がBさんだったとする．Bさんの次に対戦すべき人がAさんだった場合， 試合を行う(この状態を相思相愛と呼ぶ)．二人の対戦リストLの先頭を削除する．

このような組み合わせの2人が存在しなかった場合，条件を満たす試合の組み合わせは存在しない． このことは以下のようにして示せる．

例えばAさんの次に対戦すべき人がBさんであるが，Bさんが次に対戦すべき人はCさんだったとする． AさんとBさんが試合を行う前に，BさんはCさんと試合を行う必要があるが，そのCさんも別のDさんと 先に試合を行う必要があるという風に，どんどん依存関係が続いてしまい，最終的に矛盾が生じる．

このような考え方をした場合，以下のような素朴な解き方ができる．

int day = 0;
while(全ての人のLが空でない){
    相思相愛な人同士の組み合わせを，可能な限り見つけ，試合を行う // (1)
    Lを更新する
    day++;
}

whileループは高々N*(N-1)/2しか回らないが，(1)を素直にやろうとすると0(N)かかってしまい， 全体の計算量がO(N³)になってしまう が，これは以下のようにして高速化出来る

list ←試合を行えるリスト
listに，はじめから試合を出来る組み合わせを入れる

int day = 0;
while(listが空でない){
    listの中にある組み合わせの試合を全て行う // (2)
    Lを更新する
    (2)で試合を行った人で，次に試合が出来る組み合わせをlistに追加
    day++;
}

実装はsnukeさんの解説放送のコードが非常にわかりやすい

https://atcoder.jp/contests/abc139/submissions/7296454

トポロジカルソート

全ての試合は，N人のうちの2人の組み合わせでユニークに番号をつけることができる． ある人Aの対戦リストLについて，試合(A,L[j])は試合(A,L[i])より後に行わなければならない という依存関係がある(i < j)．

すべての試合をノードとし，依存関係を有向辺で示したグラフGを構築する． グラフGがDAGでない場合，依存関係を解消できないので条件を満たす試合の組み合わせは存在しない． 同じ人が出る試合の集合は依存関係が有るため，依存関係にない試合は同日に行える． よって答えはGの最長経路である．