ABC292E - Transitivity

考え方

アライグマ「E問題は、要するに「直接辺で繋がってないけど移動できる頂点の組の個数」を求める問題で、「移動できる頂点の組－辺の個数」なのだ！　全部の頂点からDFSすれば求められるのだ！」

— 競技プログラミングをするフレンズ (@kyopro_friends) March 4, 2023

回答例

各頂点に対し，「(到達できる頂点の数) - (直接到達できる頂点の数)」を計算する．

到達できる頂点は，DFSで求められる．DFSはスタックを使えば良い．
※BFSでもよい．BFSはキューで実装できる．

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(lambda x :int(x) - 1, input().split())
    G[u].append(v)

ans = 0
for a in range(N):
    stack = [a]
    seen = [False] * N
    seen[a] = True
    cnt_all = 0
    cnt_direct = 0
    while stack:
        cur = stack.pop()
        for chi in G[cur]:
            if seen[chi]:continue
            stack.append(chi)
            seen[chi] = True
            cnt_all += 1
            if cur == a:
                cnt_direct += 1
    ans += cnt_all
    ans -= cnt_direct

print(ans)