#HXOJ3907. 图与深度优先题一:刻录光盘

提交4 通过1
通过率25%
时间限制1000ms
内存限制512MiB

题目描述

题目描述

夏令营即将结束,组委会准备把学习资料刻录到光盘中交给营员,但空光盘数量不足,无法给每个人各发一张。

小坤发现,如果两名营员之间存在联系,那么其中一人获得资料后,另一人也可以通过 U 盘等方式得到资料;这种传递可以沿着关系链继续进行。因此,同一个关系连通块中的营员只需要一张光盘。

现有 NN 名营员,编号为 11NN,并给出他们之间的关系。请计算至少要刻录多少张光盘,才能保证所有营员最终都能得到资料。输入可能重复记录同一条关系,也可能记录某人和自己有关系。

输入格式

第一行输入两个正整数 N,MN,M。接下来 MM 行,每行输入两个整数 a,ba,b,表示营员 a,ba,b 之间存在一条双向关系。

输出格式

输出一个整数,表示至少需要刻录的光盘数量。

数据范围与约定

1<N1051<N\le10^51M1061\le M\le10^6

可见测试数据

输入数据 1

4 0

输出数据 1

4

输入数据 2

5 3
1 2
2 3
4 5

输出数据 2

2

输入数据 3

4 4
1 2
2 3
3 4
4 1

输出数据 3

1