标签-强连通分量

题意有 $N$ 头奶牛,奶牛都喜欢自己,并且有 $M$ 个单向喜欢关系。定义一头被所有奶牛喜欢的奶牛为受欢迎的,求有多少头受欢迎的奶牛。其中 $N\le 10000,M\le 50000$题解把喜欢关系转化为有向图,这样处于同一个强连通分量中的牛肯定是互相喜欢的,那么我们就可以把强连通分量给缩成点。然后反着考虑,如果一个点出度为 $0$ ,那么其他点就不可能受欢迎,受欢迎的就只有这一个点。这...
   题解    0 条评论
提高+/省选-