CF505D.Mr. Kitayuta's Technology

提高+/省选-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Shuseki Kingdom is the world's leading nation for innovation and technology. There are n cities in the kingdom, numbered from 1 to n.

Thanks to Mr. Kitayuta's research, it has finally become possible to construct teleportation pipes between two cities. A teleportation pipe will connect two cities unidirectionally, that is, a teleportation pipe from city x to city y cannot be used to travel from city y to city x. The transportation within each city is extremely developed, therefore if a pipe from city x to city y and a pipe from city y to city z are both constructed, people will be able to travel from city x to city z instantly.

Mr. Kitayuta is also involved in national politics. He considers that the transportation between the m pairs of city (a__i, b__i) (1 ≤ i ≤ m) is important. He is planning to construct teleportation pipes so that for each important pair (a__i, b__i), it will be possible to travel from city a__i to city b__i by using one or more teleportation pipes (but not necessarily from city b__i to city a__i). Find the minimum number of teleportation pipes that need to be constructed. So far, no teleportation pipe has been constructed, and there is no other effective transportation between cities.

Shuseki王国是全球创新与技术领域的领军国家。该国共有 nn 座城市,编号从 11 到 nn。

得益于北田先生(Mr. Kitayuta)的研究,如今终于可以在两座城市之间建造传送管道。每条传送管道为单向连接,即从城市 xx 到城市 yy 的传送管道无法用于从城市 yy 返回城市 xx。各城市内部的交通极为发达,因此若同时建造了从城市 xx 到城市 yy 的管道以及从城市 yy 到城市 zz 的管道,则人们便可借助这两条管道瞬间从城市 xx 到达城市 zz。

北田先生同时也参与国家政治事务。他认为 mm 对城市 (ai, bi)(a_i,\,b_i)(其中 1≤i≤m1 \le i \le m)之间的交通至关重要。他计划建造若干传送管道,使得对每一对重要城市 (ai, bi)(a_i,\,b_i),均能通过一条或多条传送管道(但不一定可反向通行)从城市 aia_i 到达城市 bib_i。请找出所需建造的最少传送管道数量。目前尚未建造任何传送管道,且城市之间不存在其他有效的交通方式。

输入格式

The first line contains two space-separated integers n and m (2 ≤ n ≤ 105, 1 ≤ m ≤ 105), denoting the number of the cities in Shuseki Kingdom and the number of the important pairs, respectively.

The following m lines describe the important pairs. The i-th of them (1 ≤ i ≤ m) contains two space-separated integers a__i and b__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i), denoting that it must be possible to travel from city a__i to city b__i by using one or more teleportation pipes (but not necessarily from city b__i to city a__i). It is guaranteed that all pairs (a__i, b__i) are distinct.

第一行包含两个以空格分隔的整数 nn 和 mm(2 ≤ n ≤ 1052 \leq n \leq 10^5,1 ≤ m ≤ 1051 \leq m \leq 10^5),分别表示修石王国的城市数量和重要城市对的数量。

接下来的 mm 行描述这些重要城市对。其中第 ii 行(1 ≤ i ≤ m1 \leq i \leq m)包含两个以空格分隔的整数 aia_i 和 bib_i(1 ≤ ai, bi ≤ n1 \leq a_i, b_i \leq n,ai ≠ bia_i \neq b_i),表示必须能够通过一条或多条传送管道从城市 aia_i 到达城市 bib_i(但不一定能从城市 bib_i 到达城市 aia_i)。保证所有对 (ai, bi)(a_i, b_i) 互不相同。

输出格式

Print the minimum required number of teleportation pipes to fulfill Mr. Kitayuta's purpose.

输出满足北山先生需求所需的最小传送管道数量。

输入输出样例

  • 输入#1

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

    输出#1

    3
  • 输入#2

    4 6
    1 2
    1 4
    2 3
    2 4
    3 2
    3 4

    输出#2

    4

说明/提示

For the first sample, one of the optimal ways to construct pipes is shown in the image below:

For the second sample, one of the optimal ways is shown below:

对于第一个样例,一种构造管道的最优方式如下图所示:

对于第二个样例,一种最优方式如下图所示:

输入解题思路,AI测评打分。不知道怎么写?

首页