传统题 100ms 32MiB

【普及】连通块个数

题目描述

注意:请分别用 bfs 和 并查集 通过本题目!!

给你一个 nn 个点 mm 条边的无向图 GG,请计算图 GG 中连通块的个数

输入格式

第一行包含 22 个整数 n,mn, m

接下来 mm 行,每行包含 22 个整数 x,yx, y,表示 xx 和 yy 之间有一条无向边

输出格式

输出连通块的个数

5 4
1 2
3 4
4 5
3 5
2

提示

【样例 1 解释】

  • 图中的 22 个连通块为 {1,2},{3,4,5}\{1, 2\}, \{3, 4, 5\}

【数据范围】

对于所有测试数据,均有:

  • 1≤n≤1051 \le n \le 10^5
  • 0≤m≤min⁡(105,n×(n−1)2)0 \le m \le \min(10^5, \frac{n \times (n - 1)}{2})
  • 1≤x,y≤n1 \le x, y \le n
请思考后再点击查看提示

来源