AtCoder Regular Contest 037
翻译中…
Problem Statement
翻译中…
バウムテストとは、被験者に「木」の絵を描かせることで被験者の心理状態を読み取る心理検査である。この検査を受けた高橋君は、 $N$ 個の頂点と $M$ 本の辺からなる無向グラフを描いた。このグラフの連結成分のうち木であるようなもの、すなわち閉路を持たないものの個数を求めよ。
翻译中…
Input
翻译中…
入力は以下の形式で標準入力から与えられる。
翻译中…
N M
u_1 v_1
u_2 v_2
:
u_M v_M
翻译中…
$1$行目には、高橋君が描いた無向グラフに含まれる頂点の数$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$本しか存在しない。
翻译中…
Output
翻译中…
標準出力に、高橋君が描いた無向グラフの連結成分のうち木であるものの個数を出力し、末尾で改行せよ。
翻译中…
样例
Input #1
8 7
1 2
2 3
2 4
5 6
6 7
6 8
7 8
Output #1
1

頂点 $1, 2, 3, 4$ からなる連結成分と頂点 $5, 6, 7, 8$ からなる連結成分の $2$ つの連結成分がある。前者には閉路が含まれず、後者には閉路 $6 - 7 - 8 - 6$ が含まれる。従って、木であるような連結成分の個数は $1$ である。
Input #2
5 1
1 2
Output #2
4

$1$ つの頂点からなる連結成分は木とみなされる。
Input #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
Output #3
0

「木」を模したグラフではあるが、ここで問題となっている木ではない。
题目信息
题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。