Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 223 D 問題 Restricted Permutation

AtCoder ABC ABC223 D問題 400 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

以下の条件をすべて満たす (1,2, \dots, N) の並び替え P は存在するか? 存在するならば, そのような並び替えのうち, 辞書式最小のものを求めよ.

  • P において, A_i は B_i よりも先に現れる (i=1,2, \dots, M)

制約

  • 1 \leq N,M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • A_i \neq B_i

解法

この問題はトポロジカルソートとして可能な結果のうち, 辞書式最小なものは何か? という問題である. そもそも, トポロジカルソートとは, 有向グラフ G=(V,A) において, 以下のようにして実行される.

  • T を空リストとする.
  • S に出次数 0 の頂点をすべて入れる.
  • S が空で無い限り, 以下を実行する.
    • S から適当な頂点 v を選び, Q から取り除く.
    • T の末尾に v を加える.
    • 頂点 v と v に入る全ての有向辺 a を全て取り除き, 出次数が 0 の頂点を全て S に加える.
  • |S|=|V| のとき, トポロジカルソートが存在し, T がその例である.

ここで, このアルゴリズムでは S から取り出す頂点に制限はない. ここで, v を S にあるもののうち, 最小のものという風に選んだ場合, トポロジカルソートが存在する場合の T は順序の定義から, 辞書式最小のトポロジカルソートになる. よって, 以下のようなアルゴリズムで求めることができる.

  • P を空リストとする.
  • Q に出次数 0 の頂点をすべて入れる.
  • Q が空で無い限り, 以下を実行する.
    • Q の最小値 v を Q から取り除く.
    • P の末尾に v を加える.
    • 頂点 v と v に入る全ての有向辺 a を全て取り除き, 出次数が 0 の頂点を全て Q に加える.
  • |P|=|V| のとき, P は辞書式最小のトポロジカルソートである.

ここで, Q のデータ構造において, 優先度付きキューを用いることにより, 計算量 O(M+N \log N) で求めることができる.