#abc284c. [abc284_c]Count Connected Components
[abc284_c]Count Connected Components
問題文
頂点に から の番号が、辺に から の番号がついた 頂点 辺の単純無向グラフが与えられます。辺 は頂点 と頂点 を結んでいます。
グラフに含まれる連結成分の個数を求めてください。
注釈
単純無向グラフ とは、単純で辺に向きの無いグラフのことをいいます。
グラフが 単純 であるとは、グラフが自己ループや多重辺を含まないことをいいます。
あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。
グラフが 連結 であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。
制約
- 入力で与えられるグラフは単純
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
入力例 1
5 3
1 2
1 3
4 5
出力例 1
2
与えられるグラフに含まれる連結成分は次の 個です。
- 頂点 および辺 からなる部分グラフ
- 頂点 および辺 からなる部分グラフ
入力例 2
5 0
出力例 2
5
入力例 3
4 6
1 2
1 3
1 4
2 3
2 4
3 4
出力例 3
1