记录编号	155861	评测结果	AAAAAAAAAA
题目名称	[HAOI 2006]受欢迎的牛	最终得分	100
用户昵称	Skyo	是否通过	通过
代码语言	C++	运行时间	0.051 s
提交时间	2015-03-31 16:31:47	内存使用	0.58 MiB

#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

vector <int> G[10005];
stack <int> S;
int n, m, pre[10005], low[10005], scc[10005], 
	scc_size[10005], scc_num, clock;
bool scc_out[10005];

void dfs(int i){
	S.push(i);
	pre[i] =  low[i] = ++clock;
	for(int k = 0, v; k < G[i].size() ; k++){
		v = G[i][k];
		if(!pre[v]) {
			dfs(v);
			low[i] = min(low[i], low[v]);
		} else if(!scc[v]) low[i] = min(low[i], pre[v]);
	}
	if(pre[i] == low[i]){
		int v = 1;
		scc[i] = ++scc_num;
		while(S.top() != i) scc[S.top()] = scc_num, S.pop(), v++;
		S.pop();
		scc_size[scc_num] = v;
	}
}

int main()
{
	freopen("cow.in","r",stdin);
	freopen("cow.out","w",stdout);
	scanf("%d %d", &n, &m);
	for(int k = 1, u, v; k <= m ; k++){
		scanf("%d %d", &u, &v);
		G[u].push_back(v); 
	}
	
	for(int k = 1; k <= n ; k++)
		if(!pre[k]) dfs(k);
		
	for(int k = 1; k <= n ; k++)
		for(int j = 0; j < G[k].size() ; j++){
			int v = G[k][j];
			if(scc[k] != scc[v]) scc_out[scc[k]] = 1;
		}	
		
	for(int k = 1; k <= scc_num ; k++)
		if(!scc_out[k]){
			printf("%d", scc_size[k]);
			return 0;
		}	
	printf("0");	
	return 0;	
}