안정적인 네트워크 (백준 2406)

전형적인 MST문제인데 첫 컴퓨터를 제외하고 MST를 형성하면 된다. 

import sys 
import heapq 

input = sys.stdin.readline 
n,m = map(int, input().split())
parent= [i for i in range(n+1)]

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

def union(a,b):
    a = find(a)
    b = find(b)
    if a<b :
        parent[b] = a
    else :
        parent[a] =b 

for i in range(m):
    x,y =map(int, input().split())
    union(x,y)
edges = []
heapq.heapify(edges)

for i in range(1,n+1):
    oneline = list(map(int, input().split()))
    for j in range(i+1, n+1):
        if i == 1 :
            continue
        else:
            heapq.heappush(edges, (oneline[j-1], i, j ))
total = 0 
cnt = 0 
toadd= []

while edges:
    cost, x,y = heapq.heappop(edges)
    if find(x) == find(y):
        continue 
    else:
        total +=cost 
        cnt += 1 
        union(x,y)
        toadd.append((x,y))
print(total, cnt )
if len(toadd)==0 :
    exit()
else :
    for i in range(len(toadd)):
        print(toadd[i][0] , toadd[i][1])