https://www.acmicpc.net/problem/1197
시간 2초, 메모리 128MB
input :
- V E(1 ≤ V ≤ 10,000)(1 ≤ E ≤ 100,000)
- A B C (A번 정점과 B번 정점이 가중치 C인 간선으로 연결)(-1000000 <= C <= 1,000,000)
output :
- 첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.
조건 :
- 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.
트리의 주된 특징 중 하나가 부모 노드가 존재한다는 것이다.
즉, 가장 길이가 짧은 엣지들부터 부모 노드를 1개로 연결시켜서 트리를 만들도록 하자.
부모 노드를 나타내는 배열이 필요하고, 새로운 엣지들이 들어올 때 마다 이들이 연결되었는지 확인해야 한다.
import sys
def find(node):
if parent[node] != node:
parent[node] = find(parent[node])
return parent[node]
def union(a, b):
parent_a = find(a)
parent_b = find(b)
if parent_a < parent_b:
parent[parent_b] = parent_a
else:
parent[parent_a] = parent_b
v, e = map(int, sys.stdin.readline().split())
parent = [i for i in range(v + 1)]
edge = []
for i in range(e):
edge.append(tuple(map(int, sys.stdin.readline().split())))
edge.sort(key=lambda x:x[2])
ans = 0
for a, b, c in edge:
if find(a) != find(b):
union(a, b)
ans += c
print(ans)
