1513：【例 1】受欢迎的牛

题目描述

原题来自：USACO 2003 Fall

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

输入格式

第一行两个整数 $N, M$；

接下来 $M$ 行，每行两个整数 $A, B$，表示牛 $A$ 认为牛 $B$ 受欢迎（给出的信息有可能重复，即有可能出现多个相同的 $(A,B)$）。

输出格式

输出一个整数，表示被除自己之外的所有牛认为是受欢迎的牛的数量。

样例

样例输入 #1

3 3
1 2
2 1
2 3

样例输出 #1

1

样例解释 #1

• $N=3$ 头牛，$M=3$ 条关系。
• 关系：$1 \to 2$，$2 \to 1$，$2 \to 3$。
• 传递性：
  • 牛 $1$ 认为牛 $2$ 受欢迎。
  • 牛 $2$ 认为牛 $1$ 和牛 $3$ 受欢迎。
  • 由于传递性，牛 $1$ 也认为牛 $3$ 受欢迎（因为 $1 \to 2 \to 3$）。
• 检查每头牛是否被除自己之外的所有牛认为受欢迎：
  • 牛 $1$：牛 $2$ 认为 $1$ 受欢迎，但牛 $3$ 不认为 $1$ 受欢迎（因为没有直接或传递关系从 $3$ 到 $1$），所以牛 $1$ 不满足。
  • 牛 $2$：牛 $1$ 认为 $2$ 受欢迎，但牛 $3$ 不认为 $2$ 受欢迎，所以牛 $2$ 不满足。
  • 牛 $3$：牛 $1$ 认为 $3$ 受欢迎（通过传递），牛 $2$ 认为 $3$ 受欢迎，且除自己外所有牛（$1$ 和 $2$）都认为 $3$ 受欢迎，所以牛 $3$ 满足。
• 输出 $1$。

数据范围

对于全部数据：

• $1 \le N \le 10^4$
• $1 \le M \le 5 \times 10^4$

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

注意：本题是强连通分量缩点的经典应用。首先用 Tarjan 算法求出所有强连通分量，然后将每个强连通分量缩成一个点，得到有向无环图（DAG）。在 DAG 中，如果存在唯一的出度为 $0$ 的强连通分量，那么这个强连通分量中的所有牛都是满足条件的（因为其他所有点都能到达该分量，且该分量内的牛相互认为受欢迎）。如果出度为 $0$ 的强连通分量不止一个，则不存在满足条件的牛（因为不同出度为 $0$ 的分量之间不能相互到达）。需要输出该强连通分量的大小。