Problem p03440 (python)

Fixed submission:
from collections import deque
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
F = []
hist = [0 for _ in range(N)]
for i in range(N):
    T = []
    if hist[i]==0:
        que = deque([i])
        hist[i]=1
        heapq.heappush(T,A[i])
        while que:
            x = que.popleft()
            for y in G[x]:
                if hist[y]==0:
                    que.append(y)
                    hist[y]=1
                    heapq.heappush(T,A[y])
        F.append(T)
K = len(F)
if K>N//2+1:        
    cnt = -1
elif K==1:
    cnt = 0
else:
    cnt = 0
    for i in range(K):
        cnt += heapq.heappop(F[i])
    F1 = []
    for T in F:
        F1 += T
    F1 = sorted(F1)
    for i in range(K-2):
        cnt += F1[i]
if cnt<0:
    print("Impossible")
else:
    print(cnt)

Buggy submission (verdict: Runtime Error):
from collections import deque
import heapq
def makeTree(i):
    V = [(A[i],i)]
    que = deque([i])
    hist[i] = 1
    while que:
        x = que.popleft()
        for y in G[x]:
            if hist[y]==0:
                heapq.heappush(V,(A[y],y))
                que.append(y)
                hist[y] = 1
    T[i] = V
N,M = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
T = {}
hist = [0 for _ in range(N)]
for i in range(N):
    if hist[i]==0:
        makeTree(i)
if N<2*(len(T)-1):
    print("Impossible")
else:
    heap = []
    for t in T:
        c,v = heapq.heappop(T[t])
        heapq.heappush(heap,(c,v,t))
    cnt = 0
    while len(heap)>=2:
        c1,v1,t1 = heapq.heappop(heap)
        c2,v2,t2 = heapq.heappop(heap)
        cnt += c1+c2
        if len(T[t1])>=len(T[t2]):
            while T[t2]:
                heapq.heappush(T[t1],heapq.heappop(T[t2]))
            del T[t2]
            c3,v3 = heapq.heappop(T[t1])
            heapq.heappush(heap,(c3,v3,t1))
        else:
            while T[t1]:
                heapq.heappush(T[t2],heapq.heappop(T[t1]))
            del T[t1]
            c3,v3 = heapq.heappop(T[t2])
            heapq.heappush(heap,(c3,v3,t2))
    print(cnt)

Buggy submission (verdict: Runtime Error):
import heapq
def makeTree(j):
    global tree
    for x in G[j]:
        if hist[x]==0:
            heapq.heappush(F[tree],(A[x],x,tree))
            hist[x] = 1
            makeTree(x)
N,M = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
if M==N-1:
    cost = 0
elif N<2*(N-M-1):
    cost = "Impossible"
else:
    n = N-M
    F = {}
    hist = [0 for _ in range(N+1)]
    tree = 0
    for j in range(N):
        if hist[j]==1:continue
        if tree not in F:F[tree]=[]
        heapq.heappush(F[tree],(A[j],j,tree))
        hist[j] = 1
        makeTree(j)
        tree += 1
    cost = 0
    B = [heapq.heappop(F[0])]
    C =sorted([heapq.heappop(F[i]) for i in range(1,n)],key=lambda x:x[0],reverse=True)
    for i in range(n-1):
        b = heapq.heappop(B)
        c = C.pop()
        indb = b[2]
        indc = c[2]
        cost += b[0]+c[0]
        if i==n-2:continue
        if len(F[indb])>0:
            heapq.heappush(B,heapq.heappop(F[indb]))
        if len(F[indc])>0:
            heapq.heappush(B,heapq.heappop(F[indc]))
print(cost)

Buggy submission (verdict: Runtime Error):
import heapq
def makeTree(j):
    global tree
    for x in G[j]:
        if hist[x]==0:
            heapq.heappush(F[tree],(A[x],x,tree))
            hist[x] = 1
            makeTree(x)
N,M = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
if M==N-1:
    cost = 0
elif N<2*(N-M-1):
    cost = "Impossible"
else:
    n = N-M
    F = {}
    hist = [0 for _ in range(N+1)]
    tree = 0
    for j in range(N):
        if hist[j]==1:continue
        if tree not in F:F[tree]=[]
        heapq.heappush(F[tree],(A[j],j,tree))
        hist[j] = 1
        makeTree(j)
        tree += 1
    if len(F)!=n:
        cost = "Impossible"
    else:
        cost = 0
        B = [heapq.heappop(F[0])]
        C =sorted([heapq.heappop(F[i]) for i in range(1,n)],key=lambda x:x[0],reverse=True)
        for i in range(n-1):
            b = heapq.heappop(B)
            c = C.pop()
            indb = b[2]
            indc = c[2]
            cost += b[0]+c[0]
            if i==n-2:continue
            heapq.heappush(B,heapq.heappop(F[indb]))
            heapq.heappush(B,heapq.heappop(F[indc]))
print(cost)

Buggy submission (verdict: Runtime Error):
import heapq
def makeTree(j):
    global tree
    for x in G[j]:
        if hist[x]==0:
            heapq.heappush(F[tree],(A[x],x,tree))
            hist[x] = 1
            makeTree(x)
N,M = map(int,input().split())
A = list(map(int,input().split()))
G = {i:[] for i in range(N)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
if M==N-1:
    cost = 0
elif N<2*(N-M-1):
    cost = "Impossible"
else:
    n = N-M
    F = {i:[] for i in range(n)}
    hist = [0 for _ in range(N+1)]
    tree = 0
    for j in range(N):
        if hist[j]==1:continue
        heapq.heappush(F[tree],(A[j],j,tree))
        hist[j] = 1
        makeTree(j)
        tree += 1
    cost = 0
    B = [heapq.heappop(F[0])]
    C =sorted([heapq.heappop(F[i]) for i in range(1,n)],key=lambda x:x[0],reverse=True)
    for i in range(n-1):
        b = heapq.heappop(B)
        c = C.pop()
        indb = b[2]
        indc = c[2]
        cost += b[0]+c[0]
        if i==n-2:continue
        heapq.heappush(B,heapq.heappop(F[indb]))
        heapq.heappush(B,heapq.heappop(F[indc]))
print(cost)