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;}