← 返回题目列表

AtCoder · arc037_b

B. 鲍姆测试

中文机器翻译题面 查看原题

問題文

鲍姆测试是一种心理测试,通过让受试者画一棵树来读取受试者的心理状态。参加这次测试的高桥, N 顶点和 M 我画了一个由书本边缘组成的无向图。求该图中树状(即没有循环)的连通分量的数量。


入力

输入将以以下格式从标准输入提供。

N M
u_1 v_1
u_2 v_2
:
u_M v_M
  • 1 线显示了 Takahashi 绘制的无向图中包含的顶点数。 N (2 ≦ N ≦ 100) 和边数 M (1 ≦ M ≦ N×(N-1)/2) 用空格分隔。在顶部 它的编号为 1 它们的编号最大为 N 。
  • 2 从行 M+1 行包含有关每一面的信息。 i+1 行目 (1 ≦ i ≦ M) 有优势 i 关系 2 顶点数 u_i, v_i (1 ≦ u_i < v_i ≦ N) 用空格分隔。其中 2 对于顶点,最多有直接连接它们的边。 1 仅存在书籍。

出力

将高桥绘制的无向图的连通分量(树)的个数输出到标准输出,并在末尾换行。 连接的组件和顶点由


入力例1

8 7
1 2
2 3
2 4
5 6
6 7
6 8
7 8

出力例1

1

頂点 1, 2, 3, 4 组成 由 5, 6, 7, 8 组成的连接组件 有 2 连接的组件。前者不包含循环,后者不包含循环。 包含 6 - 7 - 8 - 6 。因此,作为树的连通分量的数量是 1 。


入力例2

5 1
1 2

出力例2

4

1 由两个顶点组成的连通分量被视为一棵树。


入力例3

11 11
1 2
1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10
9 11
10 11

出力例3

0

虽然它是一个模仿“树”的图,但它不是这里讨论的树。