| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 42555 | Accepted: 17301 |
Description
Input
Output
Sample Input
3 3 1 2 2 1 2 3
Sample Output
1
Hint
Source
题目大意：每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这
题解：还是觉得有点难啊……别人的题解……拿来借鉴看看(真的不是很会写，哎，只会模板)
先用tarjan求出每个强连通分量，再缩点，统计每个点的出度，如果有且只有1个出度为0的点，就输出这个点包含的节点数，否则输出0.
#include<iostream> #include<cstdio> #include<vector> #include<string.h> #include<cmath> using namespace std; vector<int>g[10010]; int n,m,x,y,i,j,v,c[10010],l=0,low[10010],dfn[10010],f[10010],cnt=0,out0[10010],sum[10010],time_clock=0; void tarjan(int u){ low[u]=dfn[u]=++time_clock; c[++l]=u; for(int i=0;i<g[u].size();++i){ v=g[u][i]; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(!f[v])low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ int len=l; cnt++; while(c[l]!=u)f[c[l--]]=cnt; f[c[l--]]=cnt; sum[cnt]=len-l; } } int main() { scanf("%d%d",&n,&m); for(i=1;i<=m;++i){ scanf("%d%d",&x,&y); g[x].push_back(y); } memset(dfn,0,sizeof(dfn)); for(i=1;i<=n;++i)if(!dfn[i])tarjan(i); for(i=1;i<=n;++i) for(j=0;j<g[i].size();++j){ v=g[i][j]; if(f[i]!=f[v])out0[f[i]]++; } x=0; for(i=1;i<=cnt;++i) if(!out0[i]){ if(x>0){ printf("0"); return 0; } x=sum[i]; } printf("%d",x); return 0; }
原文：https://www.cnblogs.com/wuhu-JJJ/p/11154906.html