bzoj1051：受欢迎的牛（tarjan）

1051: [HAOI2006]受欢迎的牛

Time Limit: 10 Sec  Memory Limit: 162 MB

Description

　　每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这

种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头

牛被所有的牛认为是受欢迎的。

Input

　　第一行两个数N,M。 接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可

能出现多个A,B）

Output

　　一个数，即有多少头牛被所有的牛认为是受欢迎的。

Sample Input

3 3

1 2

2 1

2 3

Sample Output

1

HINT

100%的数据N<=10000,M<=50000

题目分析：如果有多个出度为零的点答案就是0，否则就是那个点的size，连新图重新连边都不需要。

GDKOI考前敲一下Tarjan的模板……

CODE：

#include<iostream>#include<string>#include<cstring>#include<cmath>#include<cstdio>#include<cstdlib>#include<stdio.h>#include<algorithm>using namespace std;const int maxn=10010;const int maxm=50010;struct data{	int obj;	data *Next;} e[maxm];data *head[maxn];int cur=-1;int dfn[maxn];int low[maxn];int Time=0;int sta[maxn];int sak[maxn];int tail=0;int id[maxn];int Size[maxn];int num=0;int pout[maxn];int ans=0;int n,m;void Add(int x,int y){	cur++;	e[cur].obj=y;	e[cur].Next=head[x];	head[x]=e+cur;}void Dfs(int node){	dfn[node]=low[node]=++Time;	sta[node]=1;	sak[ ++tail ]=node;	for (data *p=head[node]; p; p=p->Next)	{		int son=p->obj;		if (!sta[son])		{			Dfs(son);			low[node]=min(low[node],low[son]);		}		if (sta[son]==1) low[node]=min(low[node],low[son]);	}	if (dfn[node]==low[node])	{		Size[ ++num ]=1;		while (sak[tail]!=node)		{			int son=sak[tail];			sta[son]=2;			id[son]=num;			Size[num]++;			tail--;		}		sta[node]=2;		id[node]=num;		tail--;	}}void Tarjan(){	for (int i=1; i<=n; i++) if (!sta[i]) Dfs(i);	for (int i=1; i<=n; i++)		for (data *p=head[i]; p; p=p->Next)			if (id[i]!=id[p->obj]) pout[ id[i] ]++;}int main(){	freopen("c.in","r",stdin);	freopen("c.out","w",stdout);		scanf("%d%d",&n,&m);	for (int i=1; i<=n; i++) head[i]=NULL;	for (int i=1; i<=m; i++)	{		int a,b;		scanf("%d%d",&a,&b);		Add(a,b);	}		Tarjan();		for (int i=1; i<=num; i++)		if (!pout[i])			if (!ans) ans=i;			else			{				ans=0;				break;			}	PRintf("%d/n",Size[ans]);		return 0;}