ABC245 F - Endless Walk

atcoder.jp

■問題
有向グラフが与えられて、ある点からスタートして永遠に移動し続けることが可能な点の数
→スタートした後に、ループし続ける点の数を求める

■考え方
ある点から出ていく事が出来ない場合、その点は要件を満たす事が出来ない。
出ていくことが出来ない点を消していく。

n,m=map(int,input().split())

uv=[list(map(int,input().split())) for _ in range(m)]

desu=[0]*n
tree=[[] for _ in range(n)]
tree_rev=[[] for _ in range(n)]


for [u,v] in uv:
    tree[u-1].append(v-1)
    tree_rev[v-1].append(u-1)
    desu[u-1]+=1

from collections import deque
d = deque([])
for i in range(n):
    if desu[i]==0:
        d.append(i)

check=[0]*n

while d:
    node=d.popleft()
    check[node]=1
    for nextNode in tree_rev[node]:
        desu[nextNode]-=1
        if desu[nextNode]==0:
            d.append(nextNode)
            
print(check.count(0))