消息扩散

题目描述

有 $n$ 个城市，每两个城市之间可能存在单向道路。有 $m$ 条单向道路 $u \to v$，表示城市 $u$ 的情报员可以将消息传到城市 $v$。

为了让 $n$ 个城市的所有人都得到消息，问至少需要在多少个城市发布消息。

输入格式

第一行两个整数 $n, m$。

接下来 $m$ 行，每行两个整数 $u, v$，表示从 $u$ 到 $v$ 有一条有向边。

输出格式

一个整数，表示至少需要发布消息的城市数。

输入输出样例 #1

输入 #1

5 4
1 2
2 1
2 3
5 1

输出 #1

2

说明/提示

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le m \le 5 \times 10^5$。

样例解释

5 个城市的 SCC：$\{1, 2\}$、$\{3\}$、$\{4\}$、$\{5\}$。

DAG 中入度为 0 的 SCC：$\{4\}$（孤立）和 $\{5\}$（5→1 是出边），共 2 个。

所以至少需要在 2 个城市发布消息。

算法标签

Tarjan 缩点 + 入度统计