Tarjan 算法与 洛谷P2341[USACO03FALL/HAOI2006]受欢迎的牛G

vector<int> graph[N];
 
int dfn[N], low[N];
int timer = 0;
stack<int> stk;
bool in_stack[N];
 
int sccNode[N];
int sccNum = 0;
 
void tarjan(int u){
	// 对当前节点进行初始化
	timer ++;
	dfn[u] = low[u] = timer;
	in_stack[u] = true;
	stk.push(u);
 
	for(auto v : graph[u]){  // 遍历这个节点的每一个邻居
		if(!dfn[v]){  // 如果这个节点还没有被DFS访问过，那就对从这个节点开始继续DFS
			tarjan(v);
			low[u] = min(low[u], low[v]);  // 最后将当前这个节点（u）的最小父节点设为当前值和v的最小父节点中的更小值（因为u，v联通，所以u，v的最小父节点应该相同）
		}
		else if(in_stack[v]){  // 如果他的邻居已经在栈里面了，说明他的邻居来的更早
			low[u] = min(low[u], dfn[v]);  // 邻居来的更早就把当前节点（u）的最小父节点设为当前值和邻居遍历到位次值中的更小值
		}
	}
	
	if(low[u] == dfn[u]){  // 如果一个节点一轮下来发现自己的最小父节点就是自己DFS中被遍历到的位次，说明自己就是当前所在的强连通分支中的最高节点，该分支统计完成，开始为该分支下的所有节点进行标记
		sccNum++;  // 强连通分量数目+1（当前统计出来的数量也充当当前强连通分支的编号）
		int v;
		while(true){
			v = stk.top();  //取出当前节点栈顶的节点
			stk.pop();
			in_stack[v] = false;
			sccNode[v] = sccNum;  // 将这个节点所属的强连通分支的编号记录下来
			
			if(u == v) break;  // 如果已经弹出到父节点自己了，就可以结束了
		}
	}
}
 
int main(void){
	int n, m;cin >> n >> m;
	
	for(int i = 1;i <= m;++i){
		int x, y;cin >> x >> y;
		graph[x].push_back(y);  // 构建这张图
	}
 
	for(int i = 1;i <= n;++i){
		if(!dfn[i]) tarjan(i);
	}
 
	return 0;
}

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define mod 1000000007
using ull = unsigned long long;
using ld = long double;
using namespace std;
using ll = long long;
using pii = pair<int, int>;
 
const int N = 10005;
 
vector<int> graph[N];
 
int dfn[N], low[N];
int timer = 0;
stack<int> stk;
bool in_stack[N];
 
int sccNode[N];
int sccNum = 0;
int sccSize[N];
 
void tarjan(int u){
	timer ++;
	dfn[u] = low[u] = timer;
	in_stack[u] = true;
	stk.push(u);
	
	for(auto v : graph[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if(in_stack[v]){
			low[u] = min(low[u], dfn[v]);
		}
	}
	
	if(low[u] == dfn[u]){
		sccNum++;
		int v;
		while(true){
			v = stk.top();
			stk.pop();
			in_stack[v] = false;
			sccNode[v] = sccNum;
			sccSize[sccNum]++;
			
			if(u == v) break;
		}
	}
}
 
int out_degree[N];
 
void solve(){
	int n, m;cin >> n >> m;
	
	for(int i = 1;i <= m;++i){
		int x, y;cin >> x >> y;
		graph[x].push_back(y);
	}
	
	for(int i = 1;i <= n;++i){
		if(!dfn[i]) tarjan(i);
	}
	
	for(int u = 1;u <= n;++u){
		for(int v : graph[u]){
			if(sccNode[u] != sccNode[v]){
				out_degree[sccNode[u]]++;
			}
		}
	}
	
	int ans = 0;
	int zero_degree_num = 0;
	for(int i = 1;i <= sccNum;++i){
		if(out_degree[i] == 0){
			zero_degree_num ++;
			ans = sccSize[i];
		}
	}
	
	if(zero_degree_num == 1) cout << ans;
	else cout << 0;
	
	return;
}
 
signed main(void){
	ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t = 1;
	//cin >> t;
	while(t--){
		solve();
	} 
    
    return 0;
}