【ybt】【图论强连通课过例2】受欢迎的牛

本文主要是介绍【ybt】【图论强连通课过例2】受欢迎的牛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

受欢迎的牛

题目链接：受欢迎的牛

题目描述

在这里插入图片描述

解题思路

我们先用 $T a r j a n$ 缩点。
如果一个点没有出度，证明它是明星点。
但如果有两个点都没有出度的话，那么它们两个都无法指向，所以没有明星点。
输出找出的明星点所包括的奶牛数即可。

code

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;queue<int> q;int n,m;
int tm,tt,ans;
int v[10010];
int az[10010];
int cu[10010];
int num[10010];
int dfn[10010];
int low[10010];
int du[10010],top;
int hd[10010],tot;struct abc{int to,next;
}b[50010];void add(int x,int y)
{b[++tot]=(abc){y,hd[x]};hd[x]=tot;
}void tarjan(int x)
{dfn[x]=low[x]=++tm;du[++top]=x;az[x]=1;for(int i=hd[x];i;i=b[i].next){int y=b[i].to;if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(az[y])low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]){v[x]=++tt;num[tt]++;while(du[top]!=x)v[du[top--]]=tt,num[tt]++;top--;}
}int main()
{cin>>n>>m;for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);add(x,y);}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=n;i++)for(int j=hd[i];j;j=b[j].next){int y=b[j].to;if(v[i]!=v[y])cu[v[i]]++;}for(int i=1;i<=tt;i++){if(!cu[i]&&!ans)ans=i;else if(!cu[i]&&ans){cout<<0<<endl;return 0;}}cout<<num[ans]<<endl;
}