d[]是直接指向的入度

du[]是传递后的入度

srink是在模拟传递过程

保证tarjian和缩点过程正确

这是代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+7;
int n,m,u,v,cnt,top,tot,ans;
int dfn[maxn],low[maxn],stk[maxn],scc[maxn],d[maxn],siz[maxn],du[maxn],f[maxn];
vector<int> e[maxn],c[maxn];

void dfs(int u){
	dfn[u]=low[u]=++cnt;
	stk[++top]=u;
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i];
		if(!dfn[v]){
			dfs(v);
			low[u]=min(low[u],low[v]); 
		}else if(!scc[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		tot++;
		while(1){
			int v=stk[top--];
			scc[v]=tot,siz[tot]++;
			if(u==v) break;
		}
	}
	return ;
}

void srink(int u){
	for(int i=0;i<c[u].size();i++){
		du[c[u][i]]+=du[u]+1;
		srink(c[u][i]);
	}
	return ;
}
 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&u,&v),e[u].push_back(v);
	for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);
	for(int u=1;u<=n;u++){
		for(int j=0;j<e[u].size();j++){
			if(scc[u]!=scc[e[u][j]]){
				c[scc[u]].push_back(scc[e[u][j]]);
				d[scc[e[u][j]]]++;
			}
		}
	}
	for(int i=1;i<=tot;i++) if(!d[i]) srink(i);
	for(int i=1;i<=tot;i++){
		if(du[i]+1==tot){
			ans=siz[i];
			break;
		}
	}
	printf("%d",ans);
	return 0;
}