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

WA48分

#include<bits/stdc++.h>
using namespace std;
struct node{int x,to,next;}bian[100010];
int n,m,bcnt,head[100010];
int num,cnt;
int spz[100010],sp=1;
int vis[100010];
int ins[100010];
int dfn[100010];
int low[100010];
//////////缩点后的变量
int clr[100010];//color染色，同一个缩点是同一个颜色，颜色用cnt表示 
int out[100010];//记录每个颜色的出边个数 
int all[100010];//记录每个颜色的点的个数 
void push(int x){spz[sp++]=x;}
int pop(){
	if(sp==1)return -1;
	return spz[--sp]; 
} 
void tj(int x){
	dfn[x]=low[x]=++num;
	push(x);ins[x]=1;vis[x]=1;
	for(int k=head[x];k;k=bian[k].next){
		if(vis[bian[k].to]==0){
			tj(bian[k].to);
			low[x]=min(low[x],low[bian[k].to]);
		}
		else if(ins[bian[k].to]==1)low[x]=min(low[x],dfn[bian[k].to]);
	}
	if(low[x]==dfn[x]){
		cnt++;//分量个数++;
		int t;//这个颜色有几个点 
		do{
			t=pop();//出栈 
			ins[t]=0;clr[t]=cnt; 
			all[cnt]++;
			if(t==-1)break;
		}
		while(t!=x); 
	}
}
void add(int x,int y){
	bcnt++;
	bian[bcnt].x=x;
	bian[bcnt].to=y;
	bian[bcnt].next=head[x];
	head[x]=cnt;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;i++)
		if(vis[i]==0)tj(i);
	for(int k=1;k<=m;k++){//遍历找出边 
		if(clr[bian[k].x]!=clr[bian[k].to])//跨分量的边 
			out[bian[k].x]++; 
	}
	int sum=0,rpt;//sum:出度为0个数，rpt:哪个颜色出度为0 
	for(int i=1;i<=cnt;i++){//看有几个出度为0 
		if(out[i]==0){
			sum++;rpt=i;
		}
	}
	if(sum!=1)cout<<0;
	else cout<<all[rpt];
	return 0;
}