ABC245F - Endless Walk

考え方

以下がすごくわかりやすい．ゲームの後退解析（負けにしか遷移できない状態から考える）みたいな考え方．
Editorial - AtCoder Beginner Contest 245

トポロジカルソートっぽく実装できる（トポロジカルソート - 競プロはじめました）．

回答例

from collections import deque

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

ans = set(i for i in range(N))
q = deque()
for v in range(N):
    if outdeg[v] == 0:
        q.append(v)

while q:
    v = q.pop()
    ans.remove(v)
    for chi in IG[v]:
        outdeg[chi] -= 1
        if outdeg[chi] == 0:
            q.append(chi)

print(len(ans))