#1809. 「一本通 3.5 例 1」受欢迎的牛

「一本通 3.5 例 1」受欢迎的牛

题目描述

原题来自:USACO 2003 Fall

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

输入格式

第一行两个数 N,MN,M
接下来 MM 行,每行两个数 A,BA,B,意思是 AA 认为 BB 是受欢迎的(给出的信息有可能重复,即有可能出现多个 A,BA,B)。

输出格式

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

样例

3 3
1 2
2 1
2 3
1

只有第三头牛被除自己之外的所有牛认为是受欢迎的。

数据范围与提示

对于全部数据,1N104,1M5×1041\le N\le 10^4,1\le M\le 5\times 10^4