消息扩散（强连通分量）

首先做一遍tarjan

然后枚举每个边判断是否在同一个连通块内

在新图上跑一边入度

若入度为0，ans累计

输出即可

题面

#include<bits/stdc++.h>
using namespace std;
const int N=2e7+7;
int m,n,k,p,idx,cnt,num,ans;
struct node
{
    int nx,to;
} e[N];
bool vis[N];
stack<int> s;
int head[N],dfn[N],low[N],sum[N],color[N],in[N];
void add_edge(int a,int b)
{
    cnt++;e[cnt].to=b;e[cnt].nx=head[a];head[a]=cnt;
}
void paint(int x)
{
    s.pop();
    color[x]=num;
    sum[num]++;
    vis[x]=false;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++idx;
    s.push(x);vis[x]=true;
    for (int i=head[x];i;i=e[i].nx)
    {
        int y=e[i].to;
        if (!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if (vis[y]) low[x]=min(low[x],dfn[y]);
    }
    if (dfn[x]==low[x])
    {
        num++;
        while (s.top()!=x)
        {
            int t=s.top();
            paint(t);
        }
        paint(x);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add_edge(x,y);
    }
    for (int i=1;i<=n;i++)
    if (!dfn[i]) tarjan(i);
    for (int i=1;i<=n;i++)
    {
     for (int j=head[i];j;j=e[j].nx)
     {
         int y=e[j].to;
         if (color[i]==color[y]) continue;
         in[color[y]]++;
     }
    }
    for (int i=1;i<=num;i++)
    if (in[i]==0) ans++;
    printf("%d",ans);
    return 0; 
}