问题 2101 --3.树(tree)

2101: 3.树(tree)

题目描述

  小明终于忙玩了各种各样的课程,终于可以继续学习算法了。 他在图论书上看到了树,树有许许多多特殊的性质。小明一下子就喜欢上了这种特殊的树。 
于是,他发明了自己的对于无向图的评分方法。 
一个无向图的分数定义为,各个连通块是树的数量。 
现在给定一个n个点m条边的无向图,问在小明的评分方法下,分数为多少。 一个连通块是树,当且仅当边数比点数少1。

输入

第一行两个整数n和m,表示图的点数和边数。
第二行有m对整数,u和v表示,结点u和节点v之间有边。
给出的无向图不存在重边。

输出

输出一行包括一个整数,表示无向图的评分,也就是树的数量。 

样例输入输出

输入#1 复制
8 6
1 2
1 3
2 4
5 6
6 7
5 7
输出#1 复制
2

提示

数据范围 
20%的数据,1<=n<=2000 
100%的数据,1<=n<=100000,0<=m<=min(n*(n-1)/2,200000)

序号 标题 作者 发表时间 费用 订购数 操作