算法的重要性不言而喻,如果你想进入一家大公司,那么必须通过基础知识和业务逻辑面试以及算法面试。因此,为了提高大家的算法能力,这个公众号将从LeetCode上为大家每天提供一道算法题。
今天我们要讨论的问题是:无向图中连通分量的数目。首先,让我们看一下这道题目:
https://leetcode-cn.com/problems/number-of-connected-components-in-an-undirected-graph/
题目描述:
给定编号从0到n-1的n个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。
示例:
解题链接:https://blog.csdn.net/Scarlett_Guan/article/details/104086040
这个问题可以通过使用并查集来解决。以下是解题思路:
1. 首先创建一个大小为n的数组parent,用于存储每个节点的父节点。初始时,所有节点的父节点都是自己。
2. 对于每条无向边(u, v),将v的父节点设置为u的父节点。这样可以简化后续的查询操作。
3. 使用并查集的遍历方法,找出所有与集合root相等的连通分量的大小。
4. 连通分量的数量即为所求结果。
下面是代码实现:
```python
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
parent = list(range(n))
def find(x: int) -> int:
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
for u, v in edges:
parent[find(u)] = find(v)
ans = 0
for i in range(n):
ans += 1 if i == find(i) else 0
return ans
```
好了,今天的文章就到这里。如果觉得有所收获,请顺手点个“在看”或者转发吧,你们的支持是我最大的动力。