/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでいます。
グラフに含まれる連結成分の個数を求めてください。
注釈
単純無向グラフ とは、単純で辺に向きの無いグラフのことをいいます。
グラフが 単純 であるとは、グラフが自己ループや多重辺を含まないことをいいます。
あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。
グラフが 連結 であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。
制約
- 1 \leq N \leq 100
- 0 \leq M \leq \frac{N(N - 1)}{2}
- 1 \leq u_i, v_i \leq N
- 入力で与えられるグラフは単純
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
答えを出力せよ。
入力例 1
5 3 1 2 1 3 4 5
出力例 1
2
与えられるグラフに含まれる連結成分は次の 2 個です。
- 頂点 1, 2, 3 および辺 1, 2 からなる部分グラフ
- 頂点 4, 5 および辺 3 からなる部分グラフ
入力例 2
5 0
出力例 2
5
入力例 3
4 6 1 2 1 3 1 4 2 3 2 4 3 4
出力例 3
1
Score : 300 points
Problem Statement
You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.
Find the number of connected components in this graph.
Notes
A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.
A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.
Constraints
- 1 \leq N \leq 100
- 0 \leq M \leq \frac{N(N - 1)}{2}
- 1 \leq u_i, v_i \leq N
- The given graph is simple.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
Output
Print the answer.
Sample Input 1
5 3 1 2 1 3 4 5
Sample Output 1
2
The given graph contains the following two connected components:
- a subgraph formed from vertices 1, 2, 3, and edges 1, 2;
- a subgraph formed from vertices 4, 5, and edge 3.
Sample Input 2
5 0
Sample Output 2
5
Sample Input 3
4 6 1 2 1 3 1 4 2 3 2 4 3 4
Sample Output 3
1