#P2419. [USACO08JAN] Cow Contest S

    ID: 1427 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2008USACO深度优先搜索DFS拓扑排序Floyd

[USACO08JAN] Cow Contest S

题目描述

N(1N100) N (1 ≤ N ≤ 100) cows, conveniently numbered 1 N 1 ~ N , are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow A A has a greater skill level than cow B(1AN;1BN;AB) B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) , then cow A A will always beat cow B B .

Farmer John is trying to rank the cows by skill level. Given a list the results of M(1M4,500) M (1 ≤ M ≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

FJ的 NN1N1001 \leq N \leq 100)头奶牛们最近参加了场程序设计竞赛。在赛场上,奶牛们按 1,2,,N1, 2, \cdots, N 依次编号。每头奶牛的编程能力不尽相同,并且没有哪两头奶牛的水平不相上下,也就是说,奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮,每一轮是两头指定编号的奶牛的对决。如果编号为 AA 的奶牛的编程能力强于编号为 BB 的奶牛 (1A,BN1 \leq A, B \leq NABA \neq B),那么她们的对决中,编号为 AA 的奶牛总是能胜出。 FJ 想知道奶牛们编程能力的具体排名,于是他找来了奶牛们所有 MM1M4,5001 \leq M \leq 4,500)轮比赛的结果,希望你能根据这些信息,推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

输入格式

第一行两个用空格隔开的整数 N,MN, M

2M+12\sim M + 1 行,每行为两个用空格隔开的整数 A,BA, B ,描述了参加某一轮比赛的奶牛的编号,以及结果(每行的第一个数的奶牛为胜者)。

输出格式

输出一行一个整数,表示排名可以确定的奶牛的数目。

5 5
4 3
4 2
3 2
1 2
2 5
2

提示

样例解释:

编号为 22 的奶牛输给了编号为 1,3,41, 3, 4 的奶牛,也就是说她的水平比这 33 头奶牛都差。而编号为 55 的奶牛又输在了她的手下,也就是说,她的水平比编号为 55 的奶牛强一些。于是,编号为 22 的奶牛的排名必然为第 44,编号为 55 的奶牛的水平必然最差。其他 33 头奶牛的排名仍无法确定。