C++14(g++5.4) 解法, 执行用时: 19ms, 内存消耗: 6368K, 提交时间: 2020-05-11 18:43:53

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MX=200100;

int color_num[MX];
int color[MX];
int dfn[MX],low[MX];
int du[MX];
int n,m,cnt,sum;
vector<int>ve[MX];
stack<int>st;
bool vis[MX];

void tarjon(int x)
{
	dfn[x]=low[x]= ++cnt;
	st.push(x);
	vis[x]=1;
	for(int i:ve[x])
	{
		if(!dfn[i]){
			tarjon(i);
			low[x]=min(low[i],low[x]);
		}
		else if(vis[i]){
			low[x]=min(low[x],dfn[i]);
		}
	}
	int k;
	if(low[x]==dfn[x])
	{
		sum++;
		do{
			k=st.top();st.pop();
			vis[k]=0;
			color[k]=sum;
			color_num[sum]++;
		}while(k!=x);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int x,y,i=0;i<m;i++)
	{
		cin>>x>>y;
		ve[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			tarjon(i);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j:ve[i])
		{
			if(color[i]!=color[j])
			{
				du[color[i]]++;
			}
		}
	}
	int mx=0;
	for(int i=1;i<=sum;i++)
	{
		if(!du[i]){
			if(mx) {
				cout<<"0\n";return 0;
			}
			mx=i;
		}
	}
	cout<<color_num[mx]<<"\n";
	return 0;
}  

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

#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) 解法, 执行用时: 16ms, 内存消耗: 1996K, 提交时间: 2023-07-20 20:04:36

#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]);
}