拓扑排序（Python）

思路：拓扑排序。这题算是拓扑排序扩展的标准例题，没学过的同学可以好好学学。具体来说就是从外向内进行食物链条数的传递，传递到最内层，也就是出度为0的节点，他们的食物链条数之和就是答案

注意：本题有个踩坑点，那就是孤立点，孤立点是没有食物链的，不能计入答案中。因此，我们就可以在答案初始化的时候，排除入度和出度都为0的点，只初始化入度为0，出度为非0的点

代码：

import sys
from collections import deque

input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

def solve():
    n, m = MII()
    in_dig = [0] * (n + 1)
    out_dig = [0] * (n + 1)
    g = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v = MII()
        g[u].append(v)
        in_dig[v] += 1
        out_dig[u] += 1

    q = deque(i for i in range(1, n + 1) if in_dig[i] == 0)
    ans = [0] * (n + 1)
    for i in q:
        if out_dig[i] != 0:
            ans[i] = 1
    while q:
        for _ in range(len(q)):
            u = q.popleft()
            for v in g[u]:
                ans[v] += ans[u]
                in_dig[v] -= 1
                if in_dig[v] == 0:
                    q.append(v)

    res = 0
    for i in range(1, n + 1):
        res += ans[i] if out_dig[i] == 0 else 0
    print(res)

t = 1
# t = II()
for _ in range(t):
    solve()