实现并查集的三种基本操作实现求解连通图个数计算
时间: 2023-07-11 13:40:25 浏览: 62
好的,我来解答你的问题。
并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。它支持的操作有三个:
1. makeSet(s): 建立一个新的并查集,其中包含 s 个单元素集合。
2. unionSet(x, y): 把元素 x 和元素 y 所在的集合合并,要求 x 和 y 所在的集合不相交,如果相交则不合并。
3. findSet(x): 找到元素 x 所在的集合的代表元素,该操作也可以用于判断两个元素是否在同一个集合中。
基于并查集,我们可以很方便地求解连通图个数。具体做法是,我们将图中的每个节点看作是一个集合中的元素,然后按照边的连接情况依次合并相邻的节点所在的集合。最后,连通图的个数就等于并查集中集合的个数。
下面是并查集的 Python 代码实现:
```python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.count = 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):
rootX, rootY = self.find(x), self.find(y)
if rootX == rootY:
return
self.parent[rootX] = rootY
self.count -= 1
def getCount(self):
return self.count
```
其中,parent 数组存储了每个节点的父节点,count 表示当前并查集中集合的个数。find() 方法采用路径压缩的方式查找元素所在的集合的代表元素,union() 方法将两个集合合并,getCount() 方法返回当前并查集中集合的个数。
使用并查集求解连通图个数的 Python 代码实现如下:
```python
def countComponents(n, edges):
uf = UnionFind(n)
for edge in edges:
uf.union(edge[0], edge[1])
return uf.getCount()
```
其中,n 表示节点的个数,edges 表示边的连接情况。我们用 UnionFind 类创建一个并查集,并依次合并每条边所连接的节点。最后,调用 getCount() 方法就可以得到连通图的个数。
相关推荐
![](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)
![](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)