本文共 1115 字，大约阅读时间需要 3 分钟。

受欢迎的牛

解题思路

先缩点成一个有向无环图

AC代码

#include
   
    #include
    
     using namespace std;int n,m,ok,top,tot,ans,T,TT,du[50005],low[50005],col[50005],dfn[50005],sum[50005],stak[50005],head[50005];struct node{
   	int to,next;}a[50005];void add(int x,int y)//建边{
   	a[++tot]=(node){
   y,head[x]};	head[x]=tot;}void Tarjan(int x)//求强连通分量缩点{
   	dfn[x]=low[x]=++T;	stak[++top]=x;	for(int i=head[x];i;i=a[i].next)	{
   		int v=a[i].to;		if(!dfn[v])		{
   			Tarjan(v);			low[x]=min(low[x],low[v]);		}		else if(!col[v])low[x]=min(low[x],low[v]);	}	if(dfn[x]==low[x])	{
   		col[x]=++TT;		sum[TT]=1;		while(stak[top]!=x)		 sum[TT]++,col[stak[top--]]=TT;		top--;	}	return;}int main(){
   	scanf("%d%d",&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=head[i];j;j=a[j].next)//枚举	 {
   	 	int v=a[j].to;	 	if(col[i]!=col[v])du[col[i]]++;	 }	for(int i=1;i<=TT;i++)	 if(!du[i])ans=sum[i],ok++;	if(ok!=1)printf("0");	else printf("%d",ans);	return 0;}
    
   

谢谢

转载地址：https://blog.csdn.net/weixin_45524309/article/details/117474081 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！