题目描述

有 $N$ 头奶牛（$1 \leq N \leq 100$），编号为 $1$ 到 $N$，正在参加一场编程比赛。众所周知，有些奶牛的编程水平比另一些更高。每头奶牛都有一个固定且唯一的技能评分。

比赛采用两两对决的形式进行，共进行 $M$ 轮（$1 \leq M \leq 4,500$）。如果奶牛 $A$ 的技能评分高于奶牛 $B$（$1 \leq A \leq N$；$1 \leq B \leq N$；$A \neq B$），那么 $A$ 必定能战胜 $B$。

农夫约翰希望根据比赛结果对所有奶牛进行技能排名。给定 $M$ 轮比赛的结果，请计算有多少头奶牛的排名可以被唯一确定（即可以明确知道它在所有奶牛中的具体名次）。题目保证比赛结果不会自相矛盾。

输入格式

• 第 1 行：两个整数 $N$ 和 $M$，分别表示奶牛数量和比赛轮数。
• 第 2 行到第 $M+1$ 行：每行包含两个整数 $A$ 和 $B$，表示该轮比赛的结果（$A$ 战胜了 $B$）。

输出格式

• 第 1 行：一个整数，表示排名可以唯一确定的奶牛数量。

样例输入 1

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

样例输出 1

2

样例解释

• 奶牛 $2$ 输给了 $4$、$3$、$1$，且战胜了 $5$，因此它的排名一定是第 $4$（倒数第二）。
• 奶牛 $5$ 输给了 $2$，且没有其他比赛记录，因此它的排名一定是第 $5$（最后一名）。
• 其他奶牛（$1$、$3$、$4$）的比赛结果不足以唯一确定它们的排名，因此输出 $2$。

题目来源

USACO 2008 January Silver

补充说明

1. 排名唯一确定的条件：

   • 如果奶牛 $X$ 的技能评分严格高于 $k$ 头奶牛，并且严格低于 $N-k-1$ 头奶牛，那么它的排名就是 $k+1$。
   • 即必须明确知道有多少奶牛比它强，多少奶牛比它弱。

2. 算法思路：

   • 使用 Floyd-Warshall 算法或 DFS/BFS 计算每头奶牛的胜负传递闭包。
   • 对于每头奶牛 $i$，统计：
     • 比它强的奶牛数量（能间接战胜它的奶牛）
     • 比它弱的奶牛数量（它能间接战胜的奶牛）
   • 如果两者之和等于 $N-1$，则它的排名可以唯一确定。

3. 数据范围：

   • $N$ 较小（$\leq 100$），因此 $O(N^3)$ 的 Floyd-Warshall 算法完全可行。