题目名称	1309. [HAOI 2006]受欢迎的牛
输入输出	`cow.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	11
题目来源	cqw 于2013-03-10加入
开放分组	全部用户
提交状态
分类标签	连通性 HAOI
	分享题解

通过：269，提交：583，通过率：46.14%
ZlycerQan	100	0.000 s	0.00 MiB	C++
LGLJ	100	0.000 s	0.00 MiB	C++
ZRQ	100	0.000 s	0.00 MiB	C++
嗨嗨嗨	100	0.000 s	0.00 MiB	C++
_Itachi	100	0.000 s	0.09 MiB	C++
LCWhiStLe	100	0.000 s	0.27 MiB	C++
Youngsc	100	0.000 s	0.28 MiB	C++
rvalue	100	0.000 s	0.33 MiB	C++
_Itachi	100	0.001 s	0.08 MiB	C++
Albert S. Chang	100	0.001 s	0.11 MiB	C++

关于受欢迎的牛的近10条评论(全部评论)
leon 2019-07-05 17:12 20楼
回复 @noip : 附议，Cogs ac在洛谷只有55分，瑆の時間~無盡輪迴·林蔭 2019-06-14 23:22 19楼
回复 @noip : 附议，Cogs ac在洛谷只有55分，瑆の時間~無盡輪迴·林蔭 2019-06-14 23:22 18楼
tarjan Shirry 2017-04-22 15:54 17楼
COGS的淼数据没有“有多个SCC的出度都为0”的数据，所以不判断符合要求的SCC是否唯一也可以AC，然而POJ是有这样的数据的... Albert S. Chang 2017-04-15 16:43 16楼
VIP蒟蒻的百题纪念。 Hallmeow 2017-04-15 10:19 15楼
数据弱QwQ这能过的代码POJ 2186死活不过 rvalue 2017-01-17 09:10 14楼
邻接矩阵开不了的统计奇技淫巧证明:缩点后的图中有出度的点不是受欢迎的。假设它受欢迎，则所有点到它都有边，所以它和它的出点互达。因此不是DAG，与题设矛盾。立得受欢迎的点出度为0 然而这说明出度为0是必要条件而不是充分条件。所以要判断有几个这样的点。 Rapiz 2016-10-27 17:58 13楼
哒哒哒哒哒！ 2016-10-16 20:53 12楼
在 poj 上过不了 wa 啊啊求助 poj 2186 Skyo 2015-03-31 16:41 11楼

1309. [HAOI 2006]受欢迎的牛

★★☆ 输入文件：cow.in 输出文件：cow.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

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

【输入格式】

第 $1$ 行两个整数 $N$，$M$；

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

【输出格式】

一个数，即有多少头牛被所有的牛认为是受欢迎的。

【样例输入】

【样例输出】

【数据范围】

$10\%$ 的数据，$N \leq 20,M \leq 50$;

$30\%$ 的数据，$N \leq 1000,M \leq 20000$;

$70\%$ 的数据，$N \leq 5000,M \leq 50000$;

$100\%$ 的数据，$N \leq 10000,M \leq 50000$;