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王国是全球创新与技术领域的领军国家。该国共有 n 座城市,编号从 1 到 n。
得益于北田先生(Mr. Kitayuta)的研究,如今终于可以在两座城市之间建造传送管道。每条传送管道为单向连接,即从城市 x 到城市 y 的传送管道无法用于从城市 y 返回城市 x。各城市内部的交通极为发达,因此若同时建造了从城市 x 到城市 y 的管道以及从城市 y 到城市 z 的管道,则人们便可借助这两条管道瞬间从城市 x 到达城市 z。
北田先生同时也参与国家政治事务。他认为 m 对城市 (ai,bi)(其中 1≤i≤m)之间的交通至关重要。他计划建造若干传送管道,使得对每一对重要城市 (ai,bi),均能通过一条或多条传送管道(但不一定可反向通行)从城市 ai 到达城市 bi。请找出所需建造的最少传送管道数量。目前尚未建造任何传送管道,且城市之间不存在其他有效的交通方式。
输入格式
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.
第一行包含两个以空格分隔的整数 n 和 m(2 ≤ n ≤ 105,1 ≤ m ≤ 105),分别表示修石王国的城市数量和重要城市对的数量。
接下来的 m 行描述这些重要城市对。其中第 i 行(1 ≤ i ≤ m)包含两个以空格分隔的整数 ai 和 bi(1 ≤ ai, bi ≤ n,ai = bi),表示必须能够通过一条或多条传送管道从城市 ai 到达城市 bi(但不一定能从城市 bi 到达城市 ai)。保证所有对 (ai, bi) 互不相同。
输出格式
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测评打分。不知道怎么写?