洛谷P2341（Tarjan+缩点）

解题报告：对于Tarjan的之前的理解的更正：

• 关于low数组在同一个联通分量中并不是所有的点都是标记为该搜索树的dfn！所以用book数组充当染色的角色。
• 关于该题的大意就是如果存在两个或以上的明星牛（不在同一个联通分支中）就等于没有！并且如果某几头牛相互关注，相当于形成一个强连通分量，然后该联通分量的出度为0，并且只有一个这样的联通分量的话，这个联通分量的所有牛都是明星！

Code：

#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)1e4+5;

int n,m,tot;
bool vist[maxn];
int dfn[maxn],low[maxn];
vector<int> E[maxn];
stack<int> st;
int cnt[maxn], siz, book[maxn]; //各个强连通分量的点数
int chu[maxn]; //联通分量缩点的出度

void init() {
	for (int i = 1; i <= n; i++) {
		E[i].clear();
	}
	memset(vist, false, sizeof(vist));
	memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low));
	memset(cnt, 0, sizeof(cnt));
	memset(chu, 0, sizeof(chu));
	memset(book, 0, sizeof(book));
	tot = 0;
	siz = 0;
	while (!st.empty()) {
		st.pop();
	}

	int u,v;
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &u, &v);
		E[u].push_back(v);
	}
}

void Tarjan(int u) {
	dfn[u] = low[u] = ++tot;
	st.push(u);
	vist[u] = true; //u已经在栈中
	for (int i = 0; i < E[u].size(); i++) {
		int v = E[u][i];
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (vist[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (low[u] == dfn[u]) {
		siz++; //强连通分量的个数
		while (true) {
			int x = st.top();
			st.pop();
			vist[x] = false;
			book[x] = siz; //染色、标记
			cnt[siz]++; //该强连通分量的点数
			if (x == u) break;
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	init();
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) {
			Tarjan(i);
		}
	}
	for (int u = 1; u <= n; u++) {
		for (int i = 0; i < E[u].size(); i++) {
			int v = E[u][i];
			if (book[u] != book[v]) { //两个不属于同一个强连通分量中
				chu[book[u]]++; //u所在的缩点出度+1
			}
		}
	}
	int k = 0, idx = 0;
	for (int i = 1; i <= siz; i++) {
		if (chu[i] == 0) {
			k++;
			idx = i;
		}
	}
	if (k == 1) {
		printf("%d\n", cnt[idx]);
	} else {
		printf("0\n");
	}
	return 0;
}