学习Tarjan
受欢迎的牛
因为牛之间的关系具有传递性,所以找出有向图中的强连通子图,每个子图中的牛一定互相喜欢。
$Tarjan$缩点,只有出度为$0$的点(牛)才有可能受到其他所有牛的喜欢(图中已无环)。
如果出度为$0$的点不止$1$个,那么这几个子图中的牛都无法互相喜欢,输出$0$。
#include<bits/stdc++.h> using namespace std; const int N=1e4+5,M=5e4+5; int n,m,cnt,top,fro[N],s[N]; int tot,color,dfs[N],low[N],col[N],size[N],in[N]; struct edge{int to,nxt;}e[M]; void add(int x,int y) { e[++cnt]={y,fro[x]}; fro[x]=cnt; } void Tarjan(int u) { dfs[u]=low[u]=++tot; s[++top]=u; for(int i=fro[u];i;i=e[i].nxt) { int v=e[i].to; if(!dfs[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } else if(!col[v]) low[u]=min(low[u],dfs[v]); } if(low[u]==dfs[u]) { col[u]=++color; while(s[top]!=u) { col[s[top--]]=color; size[color]++; } top--,size[color]++; } } int main() { scanf("%d%d",&n,&m); for(int i=1,a,b;i<=m;i++) scanf("%d%d",&a,&b),add(b,a); //反向建边,统计出度变为统计入度 for(int i=1;i<=n;i++) if(!dfs[i]) Tarjan(i); for(int i=1;i<=n;i++) for(int j=fro[i];j;j=e[j].nxt) if(col[i]!=col[e[j].to]) in[col[e[j].to]]++; int ans=-1; for(int i=1;i<=color;i++) if(!in[i]) ans=~ans?0:size[i]; printf("%d",ans); }
原文:https://www.cnblogs.com/qq8260573/p/10390928.html