这是一道不是很好想的Tarjan模版题(有一点小改动),但是要是沉下心好好思考,是可以发现其中的规律的。
主体部分还是跑Tarjan,就是要维护一个am来记录这个颜色的强连通分量里元素的数量,并且不要忘记把u从栈里删掉的时候也要修改am……(真难发现啊)
另外要明白,最受欢迎的牛一定就是那个出度为0的那个强连通分量里的所有点(对于一个强连通分量中,每个点的出度不算连接这个点和这个强连通分量里另一个点的那条边),若存在两个出度为0的点,那么就没有最受欢迎的牛。
代码如下:
#include<cstdio> #include<iostream> using namespace std; #define maxn 50005 int dfn[10005],low[10005],st[maxn],co[10005],out[10005],am[10005]; int head[maxn],to[maxn],nxt[maxn]; int cnt,n,m,num,top,col; void add(int x,int y) { to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; } void Tarjan(int u) { dfn[u]=low[u]=++num; st[++top]=u; for(int i=head[u];i;i=nxt[i]) { int v=to[i]; if(!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } else if(!co[v]) low[u]=min(low[u],low[v]); } if(low[u]==dfn[u]) { co[u]=++col; while(st[top]!=u) { co[st[top]]=col; --top; am[col]++; } --top; am[col]++; } } 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=nxt[j]) { int v=to[j]; if(co[v]!=co[i]) out[co[i]]++; } int limit=0,now; for(int i=1;i<=col;i++) { if(!out[i]) { limit++; now=i; } if(limit>1) { printf("0"); return 0; } } printf("%d",am[now]); return 0; }