[BaekJoon] 백준 1922번 : 네트워크 연결

1922번 : 네트워크 연결

최소 스패닝 트리를 구하는 방법은 자다가도 일어나서 코딩 할 수 있도록 익혀야겠다.. Union-Find 를 사용하면 된다.

[[BaekJoon] 1197번 : 최소 스패닝 트리 이렇게 푸는 방법도 있지만 아주아주 느려 Pypy3 으로 제출해야 통과가 된다.

그렇기 때문에 Union-Find 는 꼭 익혀두자!

---

import sys


def find_parent(parent, node):
	if parent[node] != node:
		parent[node] = find_parent(parent, parent[node])

	return parent[node]


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


def solution():
	answer = 0
	parent = [i for i in range(node_cnt + 1)]
	edges.sort()

	for edge in edges:
		cost, a, b = edge
		if find_parent(parent, a) != find_parent(parent, b):
			union_parent(parent, a, b)
			answer += cost

	return answer


if __name__ == "__main__":
	node_cnt = int(input())
	edge_cnt = int(input())
	edges = []
	for _ in range(edge_cnt):
		start, end, cost = map(int, sys.stdin.readline().rsplit())
		edges.append((cost, start, end))

	print(solution())