登录 |
亏格计算:
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
通过
提交
标签分类
统计