ZUFEOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
ContestProblemSetList
Login
Register
问题 C: 新的改革
内存限制:256 MB
时间限制:2 S
题面:传统
评测方式:文本比较
上传者:
提交:30
通过:9
返回比赛
提交
提交记录
题目描述
Berland有n个城市,由m条双向道路连接。没有道路将一个城市连接到它自己,每对城市之间的连接不超过一条道路。你不能保证只用现有的道路就能从任何一个城市到达另一个城市。
贝兰总统决定对道路系统进行改革,并指示交通部进行这一改革。现在,每条道路都应该是单向的(只从一个城市通向另一个城市)。
为了不引起居民的极大不满,改革需要进行,以便尽可能少地出现独立的城市。如果没有道路通向一个城市,那么这个城市就被认为是孤立的,不过允许有道路从这个城市通出去。
帮助交通部找到改革后尽可能少的孤立城市。
输入格式
输入的第一行包含两个正整数,n和m--城市的数量和Berland的道路数量(2≤n≤100000,1≤m≤100000)。
接下来的m行包含道路的描述:第i条道路由两个不同的整数xi,yi决定(1≤xi,yi≤n, xi≠yi),其中xi和yi是由第i条道路连接的城市的编号。
可以保证每对城市之间不超过一条道路,但不能保证从任何城市都可以通过道路到达任何其他城市。
输出格式
打印一个整数--改革后分离的城市的最小数量。
Examples
Input
4 3 2 1 1 3 4 3
Output
1
Input
5 5 2 1 1 3 2 3 2 5 4 3
Output
0
Input
6 5 1 2 2 3 4 5 4 6 5 6
Output
1
输入样例
复制
4 3 2 1 1 3 4 3
输出样例
复制
1
数据范围与提示
在第一个样本中,允许以下道路方向。, , .
第二个样本。, , , , .
第三个样本。, , , , .
分类标签
CF659E
1600
data
structures
dfs
and
similar
dsu
graphs
greedy