2186 Popular Cows

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
int N, M;
using namespace std;

const int si = 10010;
vector<int> G[si];
int dfn[si], low[si], color[si], size[si], stk[si];
bool flag[si];

int timelag, colorcnt, stksize;
void tarjan(int id) {
	dfn[id] = low[id] = ++timelag;
	stk[stksize++] = id;
	for (int i = 0; i < G[id].size(); i++) {
		int v = G[id][i];
		if (!dfn[v]) {//dfn也是vis的标志 是否来过
			tarjan(v);
			low[id] = min(low[id], low[v]);
		}
		else if (!color[v]) {
			low[id] = min(low[id], dfn[v]);
		}
	}
	if (dfn[id] == low[id]) {//染色
		int cnt = 0;
		colorcnt++;
		while (stksize) {
			stksize--;
			int x = stk[stksize];
			color[x] = colorcnt;
			cnt++;
			if (x == id) break;
		}
		size[colorcnt] = cnt;
	}
}
int main() {
	cin >> N >> M;
	while (M--) {
		int a, b;
		scanf("%d %d", &a, &b);
		G[b].push_back(a);//反向建图
	}
	for (int i = 1; i <= N; i++) {
		if (!dfn[i]) tarjan(i);//求强连通分量 dfn也是vis的标志
	}
	
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < G[i].size(); j++) {
			int x = G[i][j];//i到x的边 但是他们不是同一个颜色的 上图的3和5是这种关系
			if (color[i] != color[x]) flag[color[x]] = 1;
			//x崇拜i 则x所处的强连通分量都崇拜i 所有与x颜色相同的都崇拜i
			//但是i不崇拜x 否则i和x是同一个强连通分量同一种颜色了 所以扩大到整个x的颜色
		}
	}
	int num = 0, ans = 0;
	for (int i = 1; i <= colorcnt; i++) {
		if (flag[i]) continue;
		num++;
		ans = size[i];
	}
	if (num != 1) ans = 0;//只会有一个被其它所有牛崇拜的强连通分量
	cout << ans << endl;
	return 0;
}