1774번: 우주신과의 교감 (그래프, MST, 크루스칼) - Fastcampus

www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

import math


def find(i):
    if parent[i] != i:
        parent[i] = find(parent[i])
    return parent[i]


def union(i, j):
    i = find(i)
    j = find(j)
    if i != j:
        parent[i] = j


N, M = map(int, input().split())
loc = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(N)]

edges = []
for i in range(1, N+1):
    for j in range(i+1, N+1):
        x1, y1 = loc[i]
        x2, y2 = loc[j]
        w = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
        edges.append((w, i, j))

edges.sort()
parent = [i for i in range(N+1)]

# 이미 연결된 간선 전처리
for _ in range(M):
    n1, n2 = map(int, input().split())
    union(n1, n2)

# MST 간선 찾기
l = 0
for w, n1, n2 in edges:
    if find(n1) != find(n2):
        union(n1, n2)
        l += w
print(f"{l:0.2f}")