1421 - 无向图中连通分量的数目

通过次数

3

提交次数

4

时间限制 : 1 秒
内存限制 : 128 MB

给定 n 个节点(编号从 0 到 n - 1)的图的无向边列表 edges,其中 edges[i] = [u, v] 表示节点 u 和节点 v 之间有一条无向边。

计算该无向图中连通分量的数量。

  • 连通图:在无向图中,如果可以从顶点 vi 到达 vj,则称 vi 和 vj 连通。如果图中任意两个顶点之间都连通,则称该图为连通图。

  • 无向图的连通分量:如果该图为连通图,则连通分量为本身;否则将无向图中的极大连通子图称为连通分量,每个连通分量都是一个连通图。

  • 无向图的连通分量个数:无向图的极大连通子图的个数。

输入

第一行为2个整数n,m,表示共有n个节点,m条边

第二行以下m行,每行2个整数,表示边的两个顶点u和v

输出

图中连通分量的数量

样例

输入

5 3
0 1
1 2
3 4

输出

2

输入

5 4
0 1
1 2
2 3
3 4

输出

1

提示

  • 1≤n≤2000
  • 1≤edges.length≤5000
  • edges[i].length == 2
  • 0≤ui≤vi<n
  • ui!=vi
  • edges 中不会出现重复的边。