1421 - 无向图中连通分量的数目
Time Limit : 1 秒
Memory Limit : 128 MB
给定 n 个节点(编号从 0 到 n - 1)的图的无向边列表 edges,其中 edges[i] = [u, v] 表示节点 u 和节点 v 之间有一条无向边。
计算该无向图中连通分量的数量。
连通图:在无向图中,如果可以从顶点 vi 到达 vj,则称 vi 和 vj 连通。如果图中任意两个顶点之间都连通,则称该图为连通图。
无向图的连通分量:如果该图为连通图,则连通分量为本身;否则将无向图中的极大连通子图称为连通分量,每个连通分量都是一个连通图。
无向图的连通分量个数:无向图的极大连通子图的个数。
Input
第一行为2个整数n,m,表示共有n个节点,m条边
第二行以下m行,每行2个整数,表示边的两个顶点u和v
Output
图中连通分量的数量
Examples
Input
5 3 0 1 1 2 3 4
Output
2
Input
5 4 0 1 1 2 2 3 3 4
Output
1
Hint
- 1≤n≤2000
- 1≤edges.length≤5000
- edges[i].length == 2
- 0≤ui≤vi<n
- ui!=vi
edges
中不会出现重复的边。