303400: CF659E. New Reform

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

New Reform

题意翻译

### 题目描述 有 $n$ 个城市,$m$ 条双向道路,没有一个城市存在自己到自己的道路,两个不同的城市间,最多有一条道路,也不能保证能从一个城市到达任意一个其他城市。 现在需要对每一条道路定向,使之成为单向道路,当然需要尽可能少地产生孤立的城市。当其他所有城市都不能到达某个城市,则称这个城市为孤立城市。要求出最少的孤立城市的个数。 ### 输入格式 第一行,两个整数,$n$ 和 $m$。 接下来 $m$ 行,每行两个整数 $x_i$ 和 $y_i$,表示一条道路连接城市 $x_i$ 和城市 $y_i$ 的双向道路。 ### 输出格式 一行,一个整数,表示最少的孤立城市的个数。 ### 数据规模与约定 $2\le n\le 100000$,$1\le m\le 100000$。 对于每一个合法的 $x_i$ 和 $y_i$,都有 $1\le x_i,y_i\le n$,且 $x_i \not\ =y_i$。

题目描述

Berland has $ n $ cities connected by $ m $ bidirectional roads. No road connects a city to itself, and each pair of cities is connected by no more than one road. It is not guaranteed that you can get from any city to any other one, using only the existing roads. The President of Berland decided to make changes to the road system and instructed the Ministry of Transport to make this reform. Now, each road should be unidirectional (only lead from one city to another). In order not to cause great resentment among residents, the reform needs to be conducted so that there can be as few separate cities as possible. A city is considered separate, if no road leads into it, while it is allowed to have roads leading from this city. Help the Ministry of Transport to find the minimum possible number of separate cities after the reform.

输入输出格式

输入格式


The first line of the input contains two positive integers, $ n $ and $ m $ — the number of the cities and the number of roads in Berland ( $ 2<=n<=100000 $ , $ 1<=m<=100000 $ ). Next $ m $ lines contain the descriptions of the roads: the $ i $ -th road is determined by two distinct integers $ x_{i},y_{i} $ ( $ 1<=x_{i},y_{i}<=n $ , $ x_{i}≠y_{i} $ ), where $ x_{i} $ and $ y_{i} $ are the numbers of the cities connected by the $ i $ -th road. It is guaranteed that there is no more than one road between each pair of cities, but it is not guaranteed that from any city you can get to any other one, using only roads.

输出格式


Print a single integer — the minimum number of separated cities after the reform.

输入输出样例

输入样例 #1

4 3
2 1
1 3
4 3

输出样例 #1

1

输入样例 #2

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

输出样例 #2

0

输入样例 #3

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

输出样例 #3

1

说明

In the first sample the following road orientation is allowed: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF659E/bbf0ca4cbc925b1d673ae3b61e28811a0ccacf51.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF659E/851f40f264708d94590f3171217fe3d9e053dcee.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF659E/a78766420998fc575b76dcce0681c08c42ea944a.png). The second sample: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF659E/bbf0ca4cbc925b1d673ae3b61e28811a0ccacf51.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF659E/43ec097315a08660c95bbf7f709c76c8ce606dd6.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF659E/f1138b32236a89525fad2b8c02b9cbfbd546dfad.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF659E/251db88dae63817bf4f821cd1c34afb5e431b414.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF659E/a78766420998fc575b76dcce0681c08c42ea944a.png). The third sample: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF659E/bbf0ca4cbc925b1d673ae3b61e28811a0ccacf51.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF659E/f1138b32236a89525fad2b8c02b9cbfbd546dfad.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF659E/2463f630c8ccc890fae1e6f138ebd6eef6182a64.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF659E/e28d0fe9fd144c4ace5d77ff789151d059a9a237.png), ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF659E/8a5be1e7dc973906ccbd327695b9e6d157596058.png).

Input

题意翻译

### 题目描述 有 $n$ 个城市,$m$ 条双向道路,没有一个城市存在自己到自己的道路,两个不同的城市间,最多有一条道路,也不能保证能从一个城市到达任意一个其他城市。 现在需要对每一条道路定向,使之成为单向道路,当然需要尽可能少地产生孤立的城市。当其他所有城市都不能到达某个城市,则称这个城市为孤立城市。要求出最少的孤立城市的个数。 ### 输入格式 第一行,两个整数,$n$ 和 $m$。 接下来 $m$ 行,每行两个整数 $x_i$ 和 $y_i$,表示一条道路连接城市 $x_i$ 和城市 $y_i$ 的双向道路。 ### 输出格式 一行,一个整数,表示最少的孤立城市的个数。 ### 数据规模与约定 $2\le n\le 100000$,$1\le m\le 100000$。 对于每一个合法的 $x_i$ 和 $y_i$,都有 $1\le x_i,y_i\le n$,且 $x_i \not\ =y_i$。

加入题单

上一题 下一题 算法标签: