luoguP2341【模板】强连通分量 / [HAOI2006]受欢迎的牛

tarjan就不讲了
首先缩点，然后发现明星只可能是缩点重新建图后，出度为零的点，否则他自己无法欢迎他自己
但是如果出度为零的点>=2个，就没有受欢迎的牛了

#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
int color[200000],cnt=0;
struct edge{
    int v,fail;
    edge(){
    }
    edge(int a,int b){
        v=a;
        fail=b;
    }
}e[400000];
int n,m,head[200000],len;
int N[200000];
void init(){
    len=0;
    memset(head,-1,sizeof(head));
}
int dfn[200000],low[200000],vis[200000];
void add(int a,int b){
    e[len]=edge(b,head[a]);
    head[a]=len++;
}
int Time;
stack<int> s;
void calc(){
	int t=s.top();
	s.pop();
	color[t]=cnt;
	N[cnt]++;
	vis[t]=0;
} 
void tarjan(int x){
	vis[x]=1;
	s.push(x);
	dfn[x]=low[x]=++Time;
	for(int i=head[x];~i;i=e[i].fail){
		if(!dfn[e[i].v]){
			tarjan(e[i].v);
			low[x]=min(low[x],low[e[i].v]);
		}else if(vis[e[i].v])low[x]=min(low[x],dfn[e[i].v]);
	}
	if(dfn[x]==low[x]){
		cnt++;
		while(s.top()!=x)calc();
		calc();
	}
}
int in[100000]; 
int x[100000],y[100000];
int main(){
	cin>>n>>m;
	init();
	for(int i=1;i<=m;i++){
		cin>>x[i]>>y[i];
		add(x[i],y[i]);
	}
	for(int i=1;i<=n;i++){
		if(!color[i])tarjan(i);
	}
	int ans=0;
	int tot=0;
	for(int i=1;i<=m;i++){
	//	cout<<color[i]<<endl;
		if(color[x[i]]!=color[y[i]]){
			in[color[x[i]]]++;
	//		cout<<color[x[i]]<<" to"<<color[y[i]]<<endl;
		}
	}	
	for(int i=1;i<=cnt;i++){
		if(!in[i]){
			tot++;
			ans=N[i];
		}
	}
//	cout<<cnt<<endl;
	if(tot==1)
	cout<<ans<<endl;
	else cout<<0<<endl;
	return 0;
}