C++(clang++ 11.0.1) 解法, 执行用时: 14ms, 内存消耗: 1152K, 提交时间: 2023-07-20 14:41:22

#include<stdio.h>
#include<cstring>
int N,M,B,csc,t,p,k,j=1,i=1,d[10002],sz[10002],sc[10002],lw[10002],dfn[10002],hd[10002],A[50002],nxt[50002];
void tj(int x){
	int y,p=hd[x];
	for(dfn[d[++k]=x]=lw[x]=++i;p;p=nxt[p])y=A[p],dfn[y]?lw[x]=sc[y]||lw[x]<dfn[y]?lw[x]:dfn[y]:(tj(y),lw[x]=lw[y]<lw[x]?lw[y]:lw[x]);
	if(lw[x]==dfn[x])for(++csc;k&&t-x;)++sz[sc[t=d[k--]]=csc];
}
int main(){
	for(scanf("%d%d",&N,&M);i<=M;hd[B]=i++)scanf("%d%d",&A[i],&B),nxt[i]=hd[B];
	for(i=0;j<=N;++j)if(!dfn[j])tj(j);
	for(memset(d,0,sizeof(d)),i=1;i<=N;++i)for(p=hd[i];p;p=nxt[p])t=sc[A[p]],d[t]+=sc[i]!=t;
	for(k=-1,i=1;i<=csc;k+=!d[i++])t=d[i]?t:i;
	printf("%d",k?0:sz[t]);
}

C++(g++ 7.5.0) 解法, 执行用时: 12ms, 内存消耗: 1672K, 提交时间: 2023-07-20 20:04:44

#include<stdio.h>
#include<cstring>
int N,M,B,csc,t,k,j=1,i=1,d[10002],sc[10002],sz[10002],lw[10002],dfn[10002],hd[10002],A[50002],nxt[50002];
void tj(int x){
	int y,p=hd[x];
	for(dfn[d[++k]=x]=lw[x]=++i;p;p=nxt[p])y=A[p],dfn[y]?lw[x]=sc[y]||lw[x]<dfn[y]?lw[x]:dfn[y]:(tj(y),lw[x]=lw[y]<lw[x]?lw[y]:lw[x]);
	if(dfn[x]==lw[x])for(++csc;t-x;)++sz[sc[t=d[k--]]=csc];
}
int main(){
	for(scanf("%d%d",&N,&M);i<=M;hd[B]=i++)scanf("%d%d",&A[i],&B),nxt[i]=hd[B];
	for(i=0;j<=N;++j)if(!dfn[j])tj(j);
	for(memset(d,0,sizeof(d)),i=1;i<=N;++i)for(j=hd[i];j;j=nxt[j])d[t=sc[A[j]]]+=sc[i]!=t;
	for(k=-1,i=1;i<=csc;++i)if(!d[i])++k,t=i;
	printf("%d",sz[k?0:t]);
}