← 返回题目列表

AtCoder · abc245_f

I. 无尽的行走

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一个简单的有向图 G 与 N 顶点和 M 边缘。顶点被标记为 Vertex 1,顶点 2, \ldots,顶点 N。 的 i第边缘 (1\leq i\leq M) 来自顶点 U_i 到顶点 V_i.

高桥将从一个顶点开始并重复行进 G 沿着有向边从一个顶点到另一个顶点。 有多少个顶点 G 有以下条件:高桥可以从该顶点开始,通过仔细选择路径无限地继续旅行?

约束

  • 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.
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M

输出

打印答案。


示例输入 1

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

示例输出 1

4

从顶点开始时 2,高桥可以无限期地继续旅行: 2 \to 3 \to 4 \to 2 \to 3 \to \cdots 从 Vertex 开始时也是如此 3 或顶点 4。 从顶点 1,他可以先去顶点 2 ,然后再次无限期地继续行驶。
另一方面,来自 Vertex 5,他根本无法动弹。

因此,四个顶点 ―Vertex 1, 2, 3,和 4― 满足条件,所以 4 。


示例输入 2

3 2
1 2
2 1

示例输出 2

2

请注意,在简单有向图中,同一对顶点之间可能存在两条方向相反的边。 另外, G 可能未连接。