stdKonjac's Blog

 要做到不可替代,就要与众不同。

【受欢迎的牛】

题目描述

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

输入格式

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

输出格式

输出一个整数,即有多少头牛被所有的牛认为是受欢迎的。如果没有满足这种条件的情况,输出“0”。

样例数据 1

输入

3 3
1 2
2 1
2 3

输出

1

备注

【样例说明】

只有牛3是受到所有牛欢迎的。

【数据范围】

10% 的数据:N≤20, M≤50
30% 的数据:N≤1000,M≤20000
70% 的数据:N≤5000,M≤50000
100% 的数据:N≤10000,M≤50000

Tarjan缩一遍点,对于一个受所有牛喜爱的牛的集合,在新图中它一定是一个没有出度的点,画画图就知道了。所以统计没有出度的点有多少个,如果有两个以上那么某两个点之间一定不能联通,也就是说没有能被所有牛喜欢的牛群,输出0即可,否则就输出唯一的那个出度为0的点包含的牛数。

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.