Problem p03440 (python)

Fixed submission:
from collections import defaultdict

class UnionFind:  # 0-index
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  # 親の番号 要素が根の場合は-(そのグループの要素数)を格納

    def find(self, x):  # 要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  # 要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):  # 要素xが属するグループに属する要素をリストで返す O(n)に注意
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):  # すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # グループの数を返す
        return len(self.roots())

    def all_group_members(self):  # {根: [グループに含まれる要素のリスト], ...}の辞書を返す O(n)に注意
        ret = defaultdict(list)
        for i in range(self.n):
            ret[self.find(i)].append(i)
        return ret

# ---------------------- #

n, m = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
XY = [tuple(int(x) for x in input().split()) for _ in range(m)]
B = [(a, i) for i, a in enumerate(A)]

uf = UnionFind(n)
for x, y in XY:
    uf.union(x, y)

k = n - m
if k == 1:
    print(0)
    exit()
if n < 2 * k - 2:
    print("Impossible")
    exit()

ans = 0
used = set()
for root, members in uf.all_group_members().items():
    tmp, i = min((A[x], x) for x in members)
    used.add(i)
    ans += tmp

B.sort(reverse=True)
count = 0
while count < k - 2:
    a, i = B.pop()
    if i in used:
        continue
    else:
        ans += a
        count += 1

print(ans)

Buggy submission (verdict: Runtime Error):
class UnionFind:  # 0-index
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  # 親の番号 要素が根の場合は-(そのグループの要素数)を格納

    def find(self, x):  # 要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  # 要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):  # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):  # すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # グループの数を返す
        return len(self.roots())

    def all_group_members(self):  # {根: [グループに含まれる要素のリスト], ...}の辞書を返す
        return {root: self.members(root) for root in self.roots()}

# ---------------------- #

from heapq import heappop, heappush

class DeletableHeap:
    def __init__(self):
        self.size = 0
        self.del_heap = []
        self.heap = []

    def push(self, x):
        heappush(self.heap, x)
        self.size += 1

    def delete(self, x):
        heappush(self.del_heap, x)
        self.size -= 1

    def top(self):
        while self.del_heap and self.heap[0] == self.del_heap[0]:
            heappop(self.heap)
            heappop(self.del_heap)
        if not self.heap:
            return None
        else:
            return self.heap[0]

    def pop(self):
        while self.del_heap and self.heap[0] == self.del_heap[0]:
            heappop(self.heap)
            heappop(self.del_heap)
        if not self.heap:
            return None
        else:
            self.size -= 1
            return self.heap

# ---------------------- #


n, m = (int(x) for x in input().split())
A = list(int(x) for x in input().split())
XY = [tuple(int(x) for x in input().split()) for _ in range(m)]

uf = UnionFind(n)
for x, y in XY:
    uf.union(x, y)

k = uf.group_count()
if k == 1:
    print(0)
    exit()
if n < 2 * k - 2:
    print("Impossible")
    exit()

heap = DeletableHeap()
ans = 0
for root, members in uf.all_group_members().items():
    tmp = 10**18
    for x in members:
        tmp = min(tmp, A[x])
        heap.push(A[x])
    ans += tmp
    heap.delete(tmp)

for _ in range(k - 2):
    ans += heap.pop()

print(ans)