并查集 python
时间: 2023-11-06 17:03:15 浏览: 56
并查集是一种树型的数据结构,用于处理一些不相交集合的合并与查询问题。它主要包含两种操作:合并和查询。合并操作是将两个元素所在的集合合并成一个集合,而查询操作是判断两个元素是否属于同一个集合。
在使用并查集时,通常需要定义一个数组来表示每个元素的父节点。初始时,每个元素的父节点都是自己。当两个元素需要合并时,只需将其中一个元素的父节点指向另一个元素的父节点即可。查询操作可以通过递归地找到元素的根节点,并判断两个元素的根节点是否相同来确定它们是否在同一个集合中。
在实现并查集时,可以使用路径压缩优化来提高查询的效率。路径压缩是指在查询过程中,将经过的节点直接指向根节点,从而减少后续查询时的查找路径长度。这样可以使得并查集的操作具有较好的时间复杂度。
以下是一个简单的并查集的Python实现:
```python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if x != self.parent[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 isConnected(self, x, y):
return self.find(x) == self.find(y)
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)