AcWing 859. Kruskal算法求最小生成树
原题链接
简单
作者:
不知名_4
,
2024-07-25 15:28:16
,
所有人可见
,
阅读 2
Python 代码
# 输入
n,m = map(int,input().split())
uvw = []
for i in range(m):
in_uvw = list(map(int,input().split()))
uvw.append(in_uvw)
# 按照边权从小到大排序,后续Kruskal遍历用
uvw.sort(lambda x:x[2])
# 集合——并查集
array_set = [-1 for i in range(n+1)]
# 并查集找根节点
def find(array,k):
root = k
while array[root] >= 0:
root = array[root]
return root
# 计算选中的边权之和
cnt_w = 0
for i in range(m):
root_u = find(array_set,uvw[i][0])
root_v = find(array_set,uvw[i][1])
if root_u != root_v:
tt = uvw[i][1]
# 合并同时路径压缩
while array_set[tt] >= 0:
p = array_set[tt]
array_set[tt] = root_u
tt = p
# if tt != root_u:
array_set[tt] = root_u
cnt_w += uvw[i][2]
# 当所有点可连成最小生成树时,并查集中1~n的所有点只有一个根节点,即array_set[1~n]<0只有一个
possibility = 0
for i in range(1,n+1):
if array_set[i] < 0:
possibility += 1
if possibility == 1:
print(cnt_w)
else:
print("impossible")