P2341 受欢迎的牛

题目描述

每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N 头牛，给你 M 对整数，表示牛 A 认为牛 B 受欢迎。这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛 A 也认为牛 C 受欢迎。你的任务是求出有多少头牛被除自己之外的所有牛认为是受欢迎的。

输入描述

第一行两个数 N，M；

接下来 M 行，每行两个数 A，B，意思是 A 认为 B 是受欢迎的（给出的信息有可能重复，即有可能出现多个 A，B）。

输出描述

输出被除自己之外的所有牛认为是受欢迎的牛的数量。

样例输入

3 31 22 12 3

样例输出

1

我们先把这道题分成两种情况来讨论

第一种情况:不存在环

首先来画一个图

观察一下每个点的出度

在这幅图中,最受欢迎的牛是3, 那么,是否是出度为零的点就最受欢迎呢?

再来看一下

此时,点4的出度也为零,但是,这张图没有最受欢迎的牛,因为条件是除自己以外,所有人都认为它受欢迎才行,所以,在没有环情况下,如果只有一个出度为零的点,就有一头最受欢迎的牛,否则一头都没有

再来看第二种情况

第二种情况:存在环

还是来画张图

这里最受欢迎的是2,3,4

结论:有环时,先把每一个环合并成一个点,在按照没有环的方案去找,最后最受欢迎的就是那个点合并前的所有点

#includeusing namespace std;const int N=1e4+5;vectora[N];int dfn[N],vis[N],id[N],size[N],low[N],cd[N];int n,m;int times;int scc;stackt;void tarjan(int x){vis[x]=1;dfn[x]=low[x]=++times;t.push(x);for(int i=0;i1){printf("0");return 0;}}}printf("%d",ans);}