并查集的三种基本操作实现求解连通图个数计算
时间: 2023-07-11 13:36:26 浏览: 55
首先,我们需要了解并查集的三种基本操作:
1. 初始化:将每个节点的父节点初始化为自己。
2. 查找:查找节点所在的集合,即找到它的根节点。
3. 合并:将两个集合合并为一个集合,即将其中一个集合的根节点指向另一个集合的根节点。
使用并查集求解连通图个数的方法如下:
1. 首先,我们需要将每个节点看做独立的集合,即将每个节点的父节点初始化为自己。
2. 对于每条边,我们将它所连接的两个节点所在的集合合并为一个集合。
3. 最后,我们遍历每个节点,找到它所在的集合的根节点,并记录下不同根节点的个数,即为连通图的个数。
下面是实现代码:
```python
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
self.parent[root_x] = root_y
def count_connected_components(n, edges):
uf = UnionFind(n)
for edge in edges:
uf.union(edge[0], edge[1])
root_set = set()
for i in range(n):
root_set.add(uf.find(i))
return len(root_set)
```
其中,n 表示节点数,edges 表示边的列表,每个边是一个包含两个节点编号的元组。count_connected_components 函数返回连通图的个数。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)