判断两个并查集有无交集
时间: 2023-12-08 20:37:54 浏览: 46
判断两个并查集是否有交集,可以通过查找它们的根节点是否相同来实现。如果两个并查集的根节点相同,则它们有交集;如果两个并查集的根节点不同,则它们没有交集。
具体实现可以通过查找两个元素的根节点,然后比较根节点是否相同来实现。如果根节点相同,则它们在同一个并查集中,否则它们不在同一个并查集中。
以下是一个示例代码:
```python
# 定义并查集类
class UnionFind:
def __init__(self, n):
self.parent = list(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 is_connected(self, x, y):
return self.find(x) == self.find(y)
```
使用示例:
```python
# 创建一个并查集对象
uf = UnionFind(5)
# 合并元素0和元素1所在的并查集
uf.union(0, 1)
# 判断元素0和元素2是否在同一个并查集中
print(uf.is_connected(0, 2)) # 输出:False
# 合并元素2和元素3所在的并查集
uf.union(2, 3)
# 判断元素0和元素2是否在同一个并查集中
print(uf.is_connected(0, 2)) # 输出:True
```