AT_abc245_f [ABC245F] Endless Walk

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的简单有向图 $G$，顶点编号为 $1$ 到 $N$。第 $i$ 条边从顶点 $U_i$ 指向顶点 $V_i$。

高桥君可以从某个顶点出发，沿着有向边不断从一个顶点移动到另一个顶点。请你求出有多少个顶点满足：高桥君可以通过巧妙地选择路径，从该顶点出发，无限次地重复移动。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_M$ $V_M$

输出格式

输出满足条件的顶点个数。

输入输出样例 #1

输入 #1

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

输出 #1

4

输入输出样例 #2

输入 #2

3 2
1 2
2 1

输出 #2

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$
• 若 $i \neq j$，则 $(U_i, V_i) \neq (U_j, V_j)$
• 所有输入均为整数。

样例解释 1

如果从顶点 $2$ 出发，可以按照“顶点 $2$ $\to$ 顶点 $3$ $\to$ 顶点 $4$ $\to$ 顶点 $2$ $\to$ 顶点 $3$ $\to$ $\cdots$”这样的路径无限次移动。从顶点 $3$、顶点 $4$ 出发也同理。如果从顶点 $1$ 出发，最初可以移动到顶点 $2$，之后也可以无限次移动。另一方面，从顶点 $5$ 出发则无法移动。
因此，满足条件的顶点为顶点 $1$、$2$、$3$、$4$，共 $4$ 个，所以输出 $4$。

样例解释 2

请注意，在简单有向图中，两个顶点之间可以同时存在方向相反的两条边。此外，$G$ 不一定是连通图。

由 ChatGPT 4.1 翻译