SZ#G6DFS11. 【GESP强化 六级】统计图的连通分量

提交1 通过1
通过率100%
时间限制2000ms
内存限制256MiB

题目描述

珅泽教育的小婷老师正在准备一项搜索实践,她请小泽完成下面的任务。

给定一张有 NN 个顶点、MM 条边的简单无向图。顶点编号为 11NN,第 ii 条边连接 uiu_iviv_i

如果两个顶点能够通过若干条边互相到达,就认为它们属于同一个连通分量。请输出整张图中连通分量的数量。孤立顶点自身也构成一个连通分量。

输入格式

第一行输入 N,MN,M

接下来 MM 行,每行输入 ui,viu_i,v_i

输出格式

输出连通分量数量。

6 4
2 1
4 1
5 3
6 1
2
9 6
3 2
4 1
5 3
7 5
8 3
9 7
3
12 9
2 1
3 2
4 1
6 5
7 1
8 6
10 1
11 5
12 11
3

数据范围与约定

  • 1N1001 \le N \le 100
  • 0MN(N1)/20 \le M \le N(N-1)/2
  • 图中没有自环和重边