ABC291 E問題 Find Permutation

atcoder.jp

有向グラフとみなしてみる

数の大小関係 を小さいほうから大きいほうへ向かう向きを持った辺と考えると、有向グラフとして扱うこともできます。
問題は、有向グラフをトポロジカルソートして、順序が一意に定まるかどうかです。

頂点 が出力辺のみで入力辺を持たない場合、一番小さな数の可能性があります。
頂点 が入力辺のみで出力辺を持たない場合、一番大きな数の可能性があります。
頂点 が入力辺も出力辺も持たない場合、順序は決まりません。

まず、一番小さな数を確定するためには、出力辺のみで入力辺を持たない頂点が1つだけ存在することが必要です。
そして、そこからの出力辺を削除したとき、出力辺のみで入力辺を持たない別の頂点が1つだけ現れるなら、これが二番目に小さな数として確定します。

このように、小さな方から確定し続けて、すべての頂点の順序が決定できるかどうかを調べればよいです。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N,M = readInts()

  edge = [Vector{Int}() for _ = 1:N]

  count = zeros(Int,N)

  for i = 1:M
    X,Y = readInts()
    push!(edge[X],Y)  # 出力辺
    count[Y] += 1     # 入力辺の数
  end

  ans = zeros(Int,N)
  list = []

  for i = 1:N
    if count[i] == 0  # 入力辺が無い
      push!(list,i)   # 最小になる可能性のある頂点リスト
    end
  end

  rank = 0
  while length(list) == 1  # 入力辺が無い頂点の数が 1つの場合だけ以下の処理を行う
    n = popfirst!(list)
    rank += 1              # 何番目に小さな数か
    ans[n] = rank
    for i = 1:length(edge[n])  # そこから出力される辺の先の頂点から、入力辺の数を 1減らす
      k = edge[n][i]
      count[k] -= 1
      if count[k] == 0    # 入力辺の数が 0 になったら、最小になる可能性のある頂点リストに追加
        push!(list,k)
      end
    end
  end

  if minimum(ans) == 0   # 未確定の頂点が残っていれば、No
    println("No")
  else
    println("Yes")
    for i = 1:N
      print(ans[i]," ")
    end
    println()
  end

end  # function solve

# main
solve()