Score : $500$ points

问题描述

我们有一个简单的有向图 $G$，包含 $N$ 个顶点和 $M$ 条边。顶点被标记为顶点 $1$、顶点 $2$、$\ldots$、顶点 $N$。第 $i$ 条边（$1\leq i\leq M$）从顶点 $U_i$ 指向顶点 $V_i$。

Takahashi 将从一个顶点开始，并沿一条有向边在图 $G$ 上重复地从一个顶点移动到另一个顶点。请问图 $G$ 中有多少个顶点满足以下条件：Takahashi 可以从该顶点开始，并通过精心选择路径无限次地继续旅行？

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have a simple directed graph $G$ with $N$ vertices and $M$ edges. The vertices are labeled as Vertex $1$, Vertex $2$, $\ldots$, Vertex $N$. The $i$-th edge $(1\leq i\leq M)$ goes from Vertex $U_i$ to Vertex $V_i$.

Takahashi will start at a vertex and repeatedly travel on $G$ from one vertex to another along a directed edge. How many vertices of $G$ have the following condition: Takahashi can start at that vertex and continue traveling indefinitely by carefully choosing the path?

Constraints

• $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$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

Output

Print the answer.

Sample Input 1

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

Sample Output 1

4

When starting at Vertex $2$, Takahashi can continue traveling indefinitely: $2$ $\to$ $3$ $\to$ $4$ $\to$ $2$ $\to$ $3$ $\to$ $\cdots$ The same goes when starting at Vertex $3$ or Vertex $4$. From Vertex $1$, he can first go to Vertex $2$ and then continue traveling indefinitely again.
On the other hand, from Vertex $5$, he cannot move at all.

Thus, four vertices ―Vertex $1$, $2$, $3$, and $4$― satisfy the conditions, so $4$ should be printed.

Sample Input 2

3 2
1 2
2 1

Sample Output 2

2

Note that, in a simple directed graph, there may be two edges in opposite directions between the same pair of vertices. Additionally, $G$ may not be connected.

update @ 2024/3/10 10:32:07