Endless Walk

题目描述

我们有一个含 $N$ 个顶点和 $M$ 条边的简单有向图 $G$。顶点被标记为 顶点 $1$、顶点 $2$、$\ldots$、顶点 $N$。 第 $i$ 条边 $(1\leq i\leq M)$ 从 顶点 $U_i$ 指向 顶点 $V_i$。 Takahashi 将从某个顶点出发，沿有向边在 $G$ 上反复从一个顶点移动到另一个顶点。 有多少个顶点满足以下条件：Takahashi 可以从该顶点出发通过谨慎选择路径无限期地继续移动？

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$

输出格式

输出答案。

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

4

3 2
1 2
2 1

2

提示

$1 \leq N \leq 2\times 10^5$ $0 \leq M \leq \min(N(N-1), 2\times 10^5)$ $1 \leq U_i,V_i\leq N$ $U_i\neq V_i$ $(U_i,V_i)\neq (U_j,V_j)$ if $i\neq j$. 输入中的所有值均为整数。当从 顶点 $2$ 出发时，Takahashi 可以无限期地继续移动：$2$ $\to$ $3$ $\to$ $4$ $\to$ $2$ $\to$ $3$ $\to$ $\cdots$ 从 顶点 $3$ 或 顶点 $4$ 出发也同理。 从 顶点 $1$ 出发，他可以先到达 顶点 $2$，然后再次无限期地继续移动。
另一方面，从 顶点 $5$ 出发，他根本无法移动。 因此，四个顶点——顶点 $1$、$2$、$3$ 和 $4$——满足条件，所以应输出 $4$。
注意，在简单有向图中，可能存在一对顶点之间方向相反的两条边。 此外，$G$ 可能不是连通的。

标签: AtCoder|abc245F

来源

AtCoder|abc245F