题目描述
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶
牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜
欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你
算出有多少头奶牛可以当明星。
输入格式：
第一行：两个用空格分开的整数：N和M
第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B
输出格式：
第一行：单独一个整数，表示明星奶牛的数量
tarjan缩点以后重新建图，如果只有一个点没有出边，那么输出这个强联通分量的大小，否则就没有明星牛。
注意 tarjan缩点时记录每条边连着两点的数组应该开的和变数一样大，我开小就wa了一个点。。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,cnt,head[],x[],y[];
int dfn[],low[],vis[],hav[],bel[],q[];
struct edge{
int next,to;
}e[];
void insert(int u,int v){
cnt++;
e[cnt].next=head[u];e[cnt].to=v;
head[u]=cnt;
}
int top,ind,k;
void tarjan(int x){
q[++top]=x;
dfn[x]=low[x]=++ind;
vis[x]=;
for(int i=head[x];i;i=e[i].next){
int s=e[i].to;
if(!dfn[s]){
tarjan(s);
low[x]=min(low[s],low[x]);
}
else if(vis[s]){
low[x]=min(dfn[s],low[x]);
}
}
int now=;
if(dfn[x]==low[x]){
k++;
while(now!=x){
now=q[top];top--;
vis[now]=;
bel[now]=k;
hav[k]++;
}
}
}
int ans;
void work(){
for(int i=;i<=k;i++){
if(!head[i]){
if(ans){
ans=;
return ;
}
else ans=hav[i];
}
}
}
int mx=;
int main(){
scanf("%d%d",&n,&m);
int u,v,t;
for(int i=;i<=m;i++){
scanf("%d%d",&x[i],&y[i]);
insert(x[i],y[i]);
}
for(int i=;i<=n;i++){
if(!dfn[i])tarjan(i);
}
cnt=;
memset(head,,sizeof head);
memset(e,,sizeof e);
for(int i=;i<=m;i++){
if(bel[x[i]]!=bel[y[i]])insert(bel[x[i]],bel[y[i]]);
}
work();
printf("%d",ans);
return ;
}