题意分析

首先我们用Tarjan算法对强连通分量进行缩点，缩点其实就是对每个强连通分量进行染色，求得他们每个节点的染色编号。 这道题其实不用重新建图，原因在于，对于缩完点后的图，题目要求统计，其实就是所有的点都能够走到的点其对应强连通分量中点的个数。 然而关键就在于如何算出所有点都能走到呢，答案也很简单，这个点的出度一定为0。 那么是否有可能多个点出度为0呢，也是有可能的，但是这就不符合题意了，因为题目中说所有的牛的都支持。当有多个点出度为0的时候，一定不是所有牛都支持的情况，所以答案为零，

如何统计所有点的出度呢？也很简单，这里直接统计每个连通分量的出度就好了， 我们原图（非缩点后的图）中的每个点的所有边进行遍历，如果他的这条边所指向的点和本节点在同一个联通分量中（看染色编号），不必理会，如果不在，那么本节点的出度加一。

最后遍历所有连通分量，统计答案即可。

代码总览

#include<bits/stdc++.h> using namespace std; const int nmax = 100000; const int INF = 0x3f3f3f3f; int low[nmax], dfn[nmax], ss[nmax], head[nmax],color[nmax], out[nmax], num[nmax]; bool visit[nmax]; typedef struct{ int nxt, to; }Edge; Edge e[nmax]; int tot,dfnnum,sccnum, top,n,m; void add(int u, int v){ e[tot].to = v; e[tot].nxt = head[u]; head[u] = tot++; } void init(){ memset(head,-1,sizeof head); top = tot = dfnnum = sccnum = 0; } void tarjan(int u){ low[u] = dfn[u] = ++ dfnnum; visit[u] = true; ss[++top] = u; for(int i = head[u]; i!=-1 ; i = e[i].nxt){ int v = e[i].to; if(!dfn[v]){ tarjan(v); low[u] = min(low[u],low[v]); }else if(visit[v]) low[u] = min(low[u], dfn[v]); } if(low[u] == dfn[u]){ visit[u] = false; color[u] = ++sccnum; num[sccnum]++; while(ss[top] != u){ color[ss[top]] = sccnum; visit[ss[top]] = false; top--; num[sccnum]++; } top--; } } void getcount(){ for(int i = 1;i<=n;++i){ for(int j = head[i]; j != -1;j = e[j].nxt){ int v = e[j].to; if(color[v] == color[i]) continue; else{ out[color[i]] ++; } } } } int main(){ scanf("%d %d",&n,&m); init(); int u,v; for(int i = 1;i<=m;++i){ scanf("%d %d",&u,&v); add(u,v); } for(int i = 1;i<=n;++i) if(!dfn[i]) tarjan(i); getcount(); int nowans = -1; for(int i = 1;i<=sccnum;++i) if(out[i] == 0 && nowans == -1) nowans = i; else if(out[i] == 0 && nowans != -1) nowans = -2; if(nowans == -1) printf("0\n"); else printf("%d\n",num[nowans]); return 0; }