登录

题目A1161:亏格

题目描述

亏格计算:
1. 如果连通分量未形成环,则亏格为0;
2. 如果连通分量形成环,循环删除度为1的点以及相应边,直至连通分量中无度为1的点,此时亏格的计算公式为genera(亏格) = edge(边数) - vertex(节点数) + 1。 
给定一个非连通的无向图,计算所有连通分量的亏格数和。 
注:两个顶点可能有多条边直接连接,图中可能存在自环边。

输入格式

第一行包含两个正整数N(0 < N ≤ 100)、M(0 ≤ M ≤ 10 000),分别代表图的顶点数和边数。
接下来的M行,每行包含两个正整数U(1 ≤ U ≤ N)、V(1 ≤ V ≤ N),表示边的两个顶点。

输出格式

输出共一行,包含一个整数,表示图的亏格数。

输入样例
7 7
1 1
1 2
1 3
2 3
3 4
4 5
6 6
输出样例
3
请选择代码的语言:

0

通过

0

提交


时间
1 Sec
内存
128 MB
上传
admin

标签分类

统计