[bzoj1051] [HAOI2006]受欢迎的牛 （Tarjan+缩点）

强连通图，缩点

---

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.

没写cstdio DEV居然没报错，交上去连续CE两发。。。mdzz

#include <iostream>

#include <stack>

#include <cstdio>

using namespace std;

const int maxn = 10000 + 5;

const int maxm = 50000 + 5;

int n,m;

int cnt;

int out[maxn];

int dfn[maxn], low[maxn],belong[maxn];

int son[maxn];

stack <int> s;

struct edge {

	int v;

	edge *next;

}e[maxm], *head[maxn];

void dfs(int u){

	dfn[u] = low[u] = ++cnt;

	s.push(u);

	for(edge *k = head[u];k;k = k->next){

		if(!dfn[k->v])dfs(k->v);

			low[u] = min(low[u],low[k->v]);

	}

	int v;

	if(dfn[u] == low[u]){

		do {

			v = s.top();s.pop();

			belong[v] = u;

			son[u]++;

		}while(v != u);

	}

}

void rebuild(){

	for(int i = 1;i <= n;i++)out[i] = -1;

	for(int i = 1;i <= n;i++)out[belong[i]] = 0;

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

		for(edge *k = head[i];k;k = k->next){

			if(belong[i] != belong[k->v])out[belong[i]]++;

		}

	}

}

int main(){

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

	for(int i = 0;i < m;i++){

		int u,v;scanf("%d%d",&u,&v);

		e[cnt] = (edge) {v,head[u]};head[u] = &e[cnt++];

	}

	cnt = 0;

	for(int i = 1;i <= n;i++)if(!dfn[i])dfs(i);

	rebuild();

	int ans = 0;

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

		if(!out[i]){

			if(ans){ans=0;break;}

			else ans = son[i];

		}

	}

	printf("%d",ans);

	return 0;

}