1 solutions
-
0
题面描述
题目要求计算一个无向图的连通块数量。输入包含两个整数
n
和m
,分别表示图中点的数量和边的数量,接着是m
行,每行两个整数u
和v
,表示点u
和点v
之间的无向边。输出应为该图的连通块数。示例输入为4
(点数)、1
(边数)和边0 1
,输出为3
,表示图中共有 3 个连通块。思路
并查集裸题,每次加边直接并查集合并,判断连通块的时候可以使用fa[i]是不是原来初始化时候设置的值。
- 初始化一个大小为
n
的数组fa
,每个元素初始为其自身,表示每个点自成一个连通块。 - 通过
Un
函数将输入的边连接的两个点合并在同一个连通块中。 - 通过遍历
fa
数组,统计根节点(即初始化时的节点值)数量,从而得到连通块的数量。
具体步骤:
- 输入点的数量
n
和边的数量m
。 - 对于每条边,通过并查集的合并操作将两个节点连接起来。
- 最后遍历
fa
数组,统计不同的根节点数目,即为连通块的数量。
代码
C++
java
python
- 初始化一个大小为
- 1
Information
- ID
- 51
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 6
- Tags
- # Submissions
- 52
- Accepted
- 24
- Uploaded By