#ABC284C. 连通块计数

连通块计数

题目描述

\hspace{15pt}给定一个有 nn 个顶点、mm 条边的简单无向图,顶点编号为 1∼n1\sim n。简单图没有自环和重边。

\hspace{15pt}若两个顶点能够沿若干条边互相到达,则称它们连通。连通块是按这种关系得到的极大顶点集合;没有连边的孤立顶点也单独构成一个连通块。请统计连通块数量。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m\left(1\leqq n\leqq100;\ 0\leqq m\leqq n(n-1)/2\right)$。

\hspace{15pt}此后 mm 行,每行输入两个整数 $u_i,v_i\left(1\leqq u_i,v_i\leqq n;\ u_i\neq v_i\right)$,代表一条双向边。保证没有重边。

输出格式

\hspace{15pt}输出一个整数,代表连通块数量。

测试样例

5 3
1 2
1 3
4 5
2

样例 1 解释

\hspace{15pt}顶点 {1,2,3}\{1,2,3\} 互相连通,顶点 {4,5}\{4,5\} 互相连通,两部分之间没有边,因此答案为 22。

5 0
5
4 6
1 2
1 3
1 4
2 3
2 4
3 4
1