题解

/*
*  @filename:~/Documents/workspace/vscode_space
 *  @author: Ly_boy
 *  @date: 2025-04-02 13:10:49  星期三
 *  @compiler: 2025 by Ly_boy, All Rights Reserved.
 */
#include <bits/stdc++.h>

#define endl "\n"
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
#define N 200005
using namespace std;

int n, m, u, v, ans, indeg[N], outdeg[N], f[N]; // indeg:入度 outdeg:出度 f:拓扑排序后每个点的所能构成的食物链
vector<int> G[N];
queue<int> q;

void topological_sort()
{
    for (int i = 1; i <= n; i++) // 选找食物链的低端
        if (indeg[i] == 0)
            q.push(i), f[i] = 1; // f[i] = 1表示每一个底端都可以构成一条食物链
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i]; // v是u的捕食者，u是食物
            f[v] += f[u]; // v的食物链数量等于v的食物链数量加上u的食物链数量
            indeg[v]--;
            if (indeg[v] == 0)
            {
                if (outdeg[v] == 0) // 出度为0,说明v是食物链的顶端
                    ans += f[v];
                else
                    q.push(v);
            }
        }
    }
    printf("%d", ans);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        indeg[v]++; // 入度+1
        outdeg[u]++; // 出度+1
    }
    topological_sort();
    return 0;
}