tarjan缩点(受欢迎的牛)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>

using namespace std;

int cnt;//计数 
int num;//时间戳 
int p;//栈的长度 
int last[200005];//上一条边的cnt 
int h[200005];//这一条边的cnt
int next_[200005];//这个点连的v2 
int dfn[200005];//该点是第几个被访问到的
int low[200005];//表示按照方向进行访问，能够访问到的最早的节点的时间戳
int stack[200005];//tarjan的栈 
bool op[200005];//判断是否进栈 
int n,m,a,b,ans;
int poi_num;//缩点的编号(个数) 
int poi_sum[50004];//第i个缩点所含的元素个数
int poi_id[50004];//第i个点所在的缩点编号 
int out_degree[50004];//出度 

inline void add( int  v1, int v2 ) {
	++ cnt;
	last[cnt] = h[v1];//v1所连的上一条边的cnt 
	h[v1] = cnt;//v1 v2边的cnt
	next_[cnt] = v2;//v1所连接的点(v2)
	return; 
}

void tarjan ( int now ) {
	dfn[now] = low[now] = ++ num;
	stack[++ p] = now;//进栈 
	op[now] = true;
	int point_cnt = h[now];//now的第一条边的cnt
	for (register int i = point_cnt; i != 0; i = last[i]) {
		if ( dfn[next_[i]] == 0 ) {//没查到过这个节点 
			tarjan( next_[i] );
			low[now] = min( low[now] , low[next_[i]] );
		}
		else {
			low[now] = min( low[now] , dfn[next_[i]] );
		}
	}
	if ( low[now] == dfn[now] ) {
		poi_num ++;//缩点编号(个数)+1 
		int temp;
		do {
			temp = stack[p];
			poi_sum[poi_num] ++;//第poi_num个缩点的元素个数加一 
			poi_id[temp] = poi_num;//第temp个点所在的缩点编号 
			op[temp] = false;
			p --;//弹出栈顶元素 
		} while ( now != temp );
	}
}

int main() {
	scanf("%d%d",&n,&m);
	for (register int i = 1; i <= m; ++i) {
		scanf("%d%d",&a,&b);
		add( a , b );
	}
	for (register int i = 1; i <= n; ++i) {
		if( dfn[i] == 0 ){
			tarjan( i );
		}
	} 
	for (register int i = 1; i <= n; ++i) {
		for (register int j = h[i]; j !=0; j = last[j]) {
			if ( poi_id[i] != poi_id[next_[j]] ) { //i与next[j]不在同一个缩点 
				out_degree[poi_id[i]] ++;//编号为poi_id[i]的缩点出度数+1 
			}
		}
	}
	for (register int i = 1; i <= poi_num; ++i) { //枚举每个缩点 
		if ( out_degree[i] == 0 ) { //编号为i的缩点的出度为0 
			if ( ans == 0 ) { //目前只有第i个缩点出度为0
				ans = poi_sum[i];
			}
			else { //目前有一个以上的缩点出度为0 
				ans = 0;
				break;
			}
			//如果出度为0的缩点个数为1，那么缩点的元素个数即为答案
			//如果出度为0的缩点个数大于1，那么答案为0
			//若出度为0的缩点个数为0，因为会形成一个更大的缩点，所以不可能 
		}
	}
	printf("%d\n",ans);
	return 0;
}