使用并查集的思想求解最小生成树问题 输入格式: n,e ;n端点数量、m边的数量 n1,n2,e1 ; n1端点1,n2端点2 e1边的权值 。。。 ;这样的信息有e行 输出格式: n1 n2 e1 生成树中的边的信息
时间: 2024-02-05 13:12:32 浏览: 25
以下是使用并查集的Kruskal算法求解最小生成树问题的Python代码:
```python
class UnionFindSet:
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):
root_x, root_y = self.find(x), self.find(y)
if root_x == root_y:
return False
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
def kruskal(n, edges):
uf = UnionFindSet(n)
edges.sort(key=lambda x: x[2])
res = []
for e in edges:
if uf.union(e[0], e[1]):
res.append(e)
return res
if __name__ == '__main__':
n, m = map(int, input().split())
edges = []
for i in range(m):
n1, n2, e = map(int, input().split())
edges.append((n1 - 1, n2 - 1, e))
res = kruskal(n, edges)
for e in res:
print(e[0] + 1, e[1] + 1, e[2])
```
输入格式中的n表示端点数量,m表示边的数量,接下来的m行表示每条边的信息。输出格式中的每行表示一条生成树中的边的信息,n1和n2表示边的两个端点,e1表示边的权值。