Responsive image

问题 3144 --树链剖分

3144: 树链剖分

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 44
[提交][状态][讨论版][命题人:]

题目描述

给你一个n个点，m条边的无向图。


现要求如果顶点u能到达顶点v（通过其他点到达也算），则u到v之间必须有一条边。


比如有三个点：1，2，3 ；以及两条边，分别为：1-2，2-3，那么点1能通过2去往3，所以1，3需要补上一条边。
当然，如果原来1-3这条边已经存在则不用再添加。
同理，单独的一个点也不需要加边。


对于给出的无向图，请你算出最后需加多少条边才能满足条件。

输入描述

第一行输入两个整数n,m，（1<=n<=10^4）（1<=m<=n-1）


接下来m行，每行两个整数u,v，(1<=u,v<=n)，表示u到v有一条无向边

输出描述

输出共一行，一个整数

样例输入

7 4
1 3
2 3
4 5
5 6

样例输出

2

提示

图论，很神奇吧



另一组样例：

输入：

8 5

1 3

2 3

5 6

4 5

5 8

输出：

4

来源

22计二郭浩 

[提交][状态]
ACM算法攻关部