BOJ - 1774 - 우주신과의 교감

import sys
import math
import heapq

def getDistance(x1, x2):
    return (
        math.sqrt(
            math.pow(x1[0] - x2[0], 2) + math.pow(x1[1] - x2[1], 2)
        )
    )

def find(parent, x):
    if (parent[x] == x): return x
    parent[x] = find(parent, parent[x])
    return parent[x]

def unionx(parent, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)
    if not rootX == rootY: parent[rootY] = rootX

def solution():
    N, M = map(int, sys.stdin.readline().split())
    graph = []
    count = 0
    parent = [i for i in range(N+1)]
    point = [[0, 0]]


    for _ in range(N):
        X, Y = map(int, sys.stdin.readline().split())
        point.append([X, Y])

    for _ in range(M):
        X, Y = map(int, sys.stdin.readline().split())
        if find(parent, X) != find(parent, Y):
            unionx(parent, X, Y)
            count += 1

    for i in range(1, N):
        for j in range(i+1, N+1):
            distance = getDistance(point[i], point[j])
            heapq.heappush(graph, [distance, i, j])

    ans = 0
    while graph:
        weight, start, end = heapq.heappop(graph)
        if find(parent, start) != find(parent, end):
            unionx(parent, start, end)
            ans += weight
            count += 1
        if count == N:
            break

    print("%0.2f"%ans)

solution()

https://www.acmicpc.net/problem/1774