P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

链接：https://www.luogu.com.cn/problem/P2341
题目：
思路：
tarjan缩点：把所有强连通分量缩成一个点，然后统计出度为0的缩点，如果只有一个，那么能成为明星的数量就是该缩点扩充后的个数；如果不止一个，那就是0.
代码：
额，就是不知道为什么debug了两节课.......

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<cmath>
#include<limits.h>
#include<climits>
#include<fstream>
#include<set>
typedef long long ll;
using namespace std;
const int N = 1e4 + 5;
int cnt;
int  low[N], num[N], dfn;
int sccno[N], stack[N], top;
int cd[N];
int countt[N];
vector<int>G[N];
void dfs(int u)//tarjan 的 dfs板子
{
	stack[top++] = u;
	low[u] = num[u] = ++dfn;
	for (int i = 0; i < G[u].size(); i++)
	{
		int v = G[u][i];
		if (!num[v])
		{
			dfs(v);
			low[u] = min(low[u], low[v]);//注意
		}
		else if (!sccno[v]) low[u] = min(low[u], num[v]);
	}
	if (num[u] == low[u])
	{
		cnt++;
		while (1)
		{
			int v = stack[--top];
			sccno[v] = cnt;
			countt[cnt]++;
			if (u == v)break;
		}
	}

}
bool jd = false;
void tarjan(int n)
{
	cnt = dfn = top = 0;
	memset(low, 0, sizeof(low));
	memset(num, 0, sizeof(num));
	memset(sccno, 0, sizeof(sccno));

	for (int i = 1; i <= n; i++)
		if (!num[i])
			dfs(i);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n, m, u, v;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> u >> v;
		G[u].push_back(v);
	}
	tarjan(n);
	//统计：如果只有一个sccno的出度为0，那么就是该sccno的数量；如果有大于1个，那么肯定不行
	//如何统计scc的出度？直接判断每个scc的点，如果子节点有通往另一个度的，跳过，否则继续；
	map<int, bool>each_scc;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < G[i].size(); j++)
		{
			if (sccno[G[i][j]] != sccno[i])
				cd[sccno[i]]++;
		}
	}
	int cnttt = 0,rec;
	for (int i = 1; i <= cnt; i++)
	{
		if (!cd[i]) { cnttt++; rec = i; }
	}
	if (cnttt == 0)cout << n;
	else if (cnttt >= 2)cout << 0;
	else cout << countt[rec];


	return 0;
}