以下是一个简单的并查集算法的Python伪代码:
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.rank = [0] * 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):
x_root = self.find(x)
y_root = self.find(y)
if self.rank[x_root] < self.rank[y_root]:
self.parent[x_root] = y_root
elif self.rank[x_root] > self.rank[y_root]:
self.parent[y_root] = x_root
else:
self.parent[y_root] = x_root
self.rank[x_root] += 1
# 使用示例
n = 10 # 元素个数
uf = UnionFind(n)
# 进行一系列合并操作
uf.union(0, 1)
uf.union(2, 3)
uf.union(4, 5)
uf.union(6, 7)
uf.union(0, 2)
uf.union(4, 6)
# 进行一系列查询操作
print(uf.find(1)) # 输出:0
print(uf.find(3)) # 输出:2
print(uf.find(5)) # 输出:4
print(uf.find(7)) # 输出:4
以上代码实现了一个简单的并查集算法,并对集合中的元素进行了合并和查询操作。具体使用时,需要根据实际需求进行相关操作。
上一篇:并查集算法没有返回预期的结果
下一篇:并查集中的边的顺序是否重要?