能否提供一个Python实现并查集的数据结构和基本操作的模板代码示例?
时间: 2024-10-28 20:06:05 浏览: 6
当然可以。在Python中,我们可以使用内置的`set`数据结构和一些额外的逻辑来实现并查集。下面是一个简单的并查集模板:
```python
class DisjointSet:
def __init__(self, elements=None):
if elements is None:
self.parent = range(max(0, len(elements) if elements else 1))
else:
self.parent = [i for i in range(len(elements))]
# 查找根节点(路径压缩)
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
# 示例
if __name__ == "__main__":
ds = DisjointSet([0, 1, 2, 3, 4])
print("初始元素:", ds.parent)
ds.union(0, 1)
ds.union(2, 3)
print("合并后:", ds.parent)
assert ds.find(0) == ds.find(1)
assert ds.find(2) == ds.find(3)
```
在这个例子中,`DisjointSet`类有`find`和`union`两个主要方法,分别用于查找某个元素的根节点(即确定它属于哪一棵树)和将两个集合合并成一个。
阅读全文