P2341 [HAOI2006]受欢迎的牛

P2341 [HAOI2006]受欢迎的牛

塔尔羊标准模板（我才不会告诉你我嘴里含着一个九省联考的出题人）

不会劈配、林克卡特树、制胡窜

我还会叉粪宿主，梳妆素组，西安段素

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

vector<int>line[50000];

int dfn[10100],low[10100],tim;

bool instack[10100];

int stack[101000],top;

int belong[10100],cnt;

int num[10100];

int cot[10100];

void tarjan(int now)

{

	dfn[now]=low[now]=++tim;

	stack[++top]=now;

	instack[now]=true;

	for(int i=0;i<line[now].size();i++)

	{

		int nxt=line[now][i];

		if(!dfn[nxt])

		{

			tarjan(nxt);

			low[now]=min(low[nxt],low[now]);

		}

		else

			if(instack[nxt]&&dfn[nxt]<low[now])

				low[now]=dfn[nxt];

	}

	if(low[now]==dfn[now])

	{

		int pas;

		cnt+=1;

		do

		{

			pas=stack[top--];

			instack[pas]=false;

			belong[pas]=cnt;

			num[cnt]+=1;

		}while(pas!=now);

	}

	return ;

}

int main()

{

	int n,m;

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i=1;i<=m;i++)

	{

		scanf("%d%d",&a,&b);

		line[a].push_back(b);

	}

	for(int i=1;i<=n;i++)

		if(!dfn[i])

			tarjan(i);

	for(int i=1;i<=n;i++)

		for(int j=0;j<line[i].size();j++)

			if(belong[i]!=belong[line[i][j]])

				cot[belong[i]]=1;

	int ans=0;

	int pas;

	for(int i=1;i<=cnt;i++)

		if(!cot[i])

			ans+=1,pas=i;

	if(ans==1)

		printf("%d",num[pas]);

	else

		printf("0");

	return 0;

}

日常赛高