ABC292 E問題 Transitivity

単純グラフ：多重辺も自己ループももたないグラフ
有向グラフ：辺に向きがある（矢印）グラフ

条件から、「頂点 b を中心として、"入ってくる辺 a → b"と"出ていく辺 b → c"の各ペアについて、
bの相手の頂点を直接結ぶ辺 a → c が無ければ追加する」
という処理を繰り返せば答えが求まりそうですが、制限時間内に完了しません。
そこで工夫が必要になります。

例えば、辺をたどっていって、 a → b → c → d → e と頂点がつながっている場合、
a → c の辺を追加することになります。すると a → c → d となって、a → d の辺も追加することになります。
さらに a → d → e となることで、a → e の辺も追加することになります。

このように、ある頂点から辺をたどって到達できる頂点のうち、直接辺でつながっていない頂点に辺を追加することになります。

辺を追加しても、各頂点からスタートしたときに到達可能な頂点に変更はありませんので、
各頂点から到達可能な頂点のリストを1回ずつ求めて必要な辺の数を加算していけば答えが求まります。

コード例 (Julia)

function solve()

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

  N,M = readInts()

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

  for i = 1:M
    u,v = readInts()
    push!(edge[u],v)  # u から v へ向かう辺
  end

  ans = 0

  for i=1:N
    # 頂点 i から辺を通って行くことができる頂点をリストアップする
    v = zeros(Int,N)
    l = []

    # 直接辺がつながっている頂点
    for j=1:length(edge[i])
      to = edge[i][j]
      v[to] = 1
      push!(l,to)
    end

    # 辺をたどっていく
    while length(l) > 0
      next = pop!(l)
      for j=1:length(edge[next])
        to = edge[next][j]
        if v[to] == 0
          v[to] = 1
          push!(l,to)
        end
      end
    end

    # スタートの頂点および直接辺がつながっている頂点には辺を結ぶ必要はない
    v[i] = 0
    for j=1:length(edge[i])
      to = edge[i][j]
      v[to] = 0
    end

    # 頂点 i から辺を通って行くことができるけれど直接つながっていない頂点の数
    ans += sum(v)
  end

  println(ans)

end  # function solve

# main
solve()