[アルゴリズム概念]最小伸長ツリー-クルーズアルゴリズム
1151 ワード
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드의 개수, 간선의 개수
v, e = map(int, input().split())
parent = [0] * (v+1)
edges = []
result = 0
for i in range(1, v+1):
parent[i] = i
for _ in range(e):
a, b, cost = map(int, input().split())
# 비용순으로 정렬하기 위해 튜플의 첫번째 원소를 비용으로 설정
edges.append((cost, a, b))
edges.sort()
for edge in edges:
cost, a, b = edge
# 사이클이 발생하지 않는 경우에만 집합에 포함
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(result)
Reference
この問題について([アルゴリズム概念]最小伸長ツリー-クルーズアルゴリズム), 我々は、より多くの情報をここで見つけました https://velog.io/@zizudana/알고리즘개념-최소신장트리-클루스칼-알고리즘テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol