Pro.ID22833 TitlePopular Cows Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22833 AC23 Submit109 Ratio21.10% 时间&空间限制描述Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 ≤ N ≤ 10,000) cows, you are given up to M (1 ≤ M ≤ 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow. 输入Multiple test case. For each case : Line 1: Two space-separated integers, N and M Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular. 输出Description Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 ≤ N ≤ 10,000) cows, you are given up to M (1 ≤ M ≤ 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow. Input Multiple test case. For each case : Line 1: Two space-separated integers, N and M Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular. Output For each case, output one line : A single integer that is the number of cows who are considered popular by every other cow. Sample Input 3 3 Sample Output 1 Hint Cow 3 is the only cow of high popularity. Source 样例输入3 3 样例输出1 提示Cow 3 is the only cow of high popularity. |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-6 01:06 , Processed in 0.037688 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
