백준 1774 - 우주신과의 교감 (파이썬)

미리 연결된 좌표들은 먼저 유니온 연산을 했고 연결되지 않은 좌표들은 크루스칼 알고리즘을 사용했습니다.

import sys
import math

input = sys.stdin.readline

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

def union(a, b, c):
    global result
    a = find(a)
    b = find(b)
    
    if a != b:
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
        result += c
        
N, M = map(int, input().split())
parent = [i for i in range(N)]
stars = [list(map(float, input().split())) for _ in range(N)]
edges = []
result = 0

for _ in range(M):
    x, y = map(int, input().split())
    union(x - 1, y - 1, 0.0)

for i in range(N - 1):
    for j in range(i + 1, N):
        edges.append((math.sqrt((stars[i][0] - stars[j][0])**2 + (stars[i][1] - stars[j][1])**2), i, j))
       
edges.sort()

for cost, x, y in edges:
    union(x, y, cost)
        
print('%.2f' % (result))