AcWing 164. 可达性统计
原题链接
中等
作者:
不染是非
,
2025-06-06 19:24:16
· 陕西
,
所有人可见
,
阅读 2
from collections import deque
n, m = map(int, input().split())
g = [[] for i in range(n + 1)]
din = [0] * (n + 1)
for i in range(m):
a, b = map(int, input().split())
g[a].append(b)
din[b] += 1
path = []
def topsort():
q = deque()
for i in range(1, n + 1):
if din[i] == 0:
q.append(i)
path.append(i)
while q:
i = q.popleft()
for j in g[i]:
din[j] -= 1
if din[j] == 0:
q.append(j)
path.append(j)
topsort()
f = [set() for i in range(n + 1)]
for i in path[::-1]:
f[i].add(i)
for j in g[i]:
f[i] |= f[j]
for i in range(1, n + 1):
print(len(f[i]))