欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

p1233 最受欢迎的牛

程序员文章站 2022-05-26 17:54:21
...

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;
}
posted @ 2018-12-09 10:57 hsm-eternity 阅读(...) 评论(...) 编辑 收藏