p1233 最受欢迎的牛

题目

https://www.luogu.org/problemnew/show/P2341

代码

#include<bits/stdc++.h>
#define M 51000
#define N 11000
using namespace std;
inline int read()
{
	int f=1,num=0;
	char ch=getchar();
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	while (ch>='0'&&ch<='9') num=(num<<1)+(num<<3)+ch-'0', ch=getchar();
	return num*f;
}
int n,m,tot,a[M],b[M];
int dfn[N],low[N],id=0;
int ver[M],Next[M],head[M],len;
void insert(int x,int y)
{
	ver[++len]=y,Next[len]=head[x],head[x]=len;
}
int Stack[N],bel[N],size[N],mark[N],top;
bool instack[N];
void Tarjan(int x)
{
	dfn[x]=low[x]=++id;
	Stack[++top]=x;
	instack[x]=1;
	for (int i=head[x],y;i;i=Next[i])
	{
		if (!dfn[y=ver[i]])
		{
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if (instack[y])
			low[x]=min(low[x],dfn[y]);
	}
		
	if (dfn[x]==low[x])
	{
		int k; ++tot;
		do
		{
			k=Stack[top--];
			instack[k]=0;
			bel[k]=tot;
			size[tot]++;
		}while (k!=x);
	}
}
int main()
{
	n=read(),m=read();
	for (int i=1;i<=m;i++)
	{
		a[i]=read(),b[i]=read();
		insert(a[i],b[i]);
	}
	memset(instack,0,sizeof(instack));
	for (int i=1;i<=n;i++)
		if (!dfn[i]) Tarjan(i);
	for (int i=1;i<=m;i++)
		if (bel[a[i]]!=bel[b[i]])
			mark[bel[a[i]]]++;
	int ans=0;
	for (int i=1;i<=tot;i++)
		if (!mark[i])
		{
			if (ans)
			{
				printf("0\n");
				return 0;
			}
			ans=i;
		}
	printf("%d",size[ans]);
	return 0;
}