Problem p03440 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
from collections import deque

n,m = map(int,input().split())
if m == n-1:
  print(0)
  exit()
if 2*(n-m-1) > n:
    print("Impossible")
    exit()

e = [[] for i in range(n)]
a = list(map(int,input().split()))
for i in range(m):
    x,y = map(int,input().split())
    e[x].append(y)
    e[y].append(x)

def dfs(x):
    l = []
    d[x] = 1
    l.append(a[x])
    q = deque([])
    q.append(x)
    while q:
        now = q.pop()
        for nex in e[now]:
            if d[nex] > 0:
                continue
            l.append(a[nex])
            d[nex] = 1
            q.append(nex)
    l.sort()
    ans = l[0]
    
    for i in l[1:]:
        h.append(i)
    return ans
count = 2*(n-m-1)
d = [-1]*n
ans = 0
h = []
for i in range(n):
    if d[i] < 0:
        ans += dfs(i)
        count -= 1
if count > 0:
    h.sort()
    ans += sum(h[:count])
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
if n == 1:
  print(0)
  exit()
if m*2 < n:
    print("Impossible")
    exit()

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

u = Unionfind(n)
a = list(map(int,input().split()))
for i in range(m):
    x,y = map(int,input().split())
    u.union(x,y)

l = [[] for i in range(n)]
for i in range(n):
    x = u.find(i)
    if x < 0:
        heapq.heappush(l[i],a[i])
    else:
        heapq.heappush(l[x],a[i])

h = []
for i in range(n):
    if l[i]:
        x = heapq.heappop(l[i])
        heapq.heappush(h,[x,i])
ans = 0
while len(h) > 1:
    a = heapq.heappop(h)
    b = heapq.heappop(h)
    ans += a[0]+b[0]
    heapq.merge(l[a[1]],l[b[1]])
    x = heapq.heappop(l[a[1]])
    heapq.heappush(h,[x,a[1]])
    
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
if n == 1:
  print(0)
  exit()
if m*2 < n:
    print("Impossible")
    exit()

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

u = Unionfind(n)
a = list(map(int,input().split()))
for i in range(m):
    x,y = map(int,input().split())
    u.union(x,y)

l = [[] for i in range(n)]
for i in range(n):
    x = u.find(i)
    if x < 0:
        heapq.heappush(l[i],a[i])
    else:
        heapq.heappush(l[x],a[i])

h = []
for i in range(n):
    if l[i]:
        x = heapq.heappop(l[i])
        heapq.heappush(h,[x,i])
ans = 0
while len(h) > 1:
    a = heapq.heappop(h)
    b = heapq.heappop(h)
    ans += a[0]+b[0]
    l[a[1]] = list(heapq.merge(l[a[1]],l[b[1]]))
    x = heapq.heappop(l[a[1]])
    heapq.heappush(h,[x,a[1]])
    
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
n,m = map(int,input().split())
if n == 1:
  print(0)
  exit()
if m*2 < n:
    print("Impossible")
    exit()

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

u = Unionfind(n)
a = list(map(int,input().split()))
for i in range(m):
    x,y = map(int,input().split())
    u.union(x,y)

l = [[] for i in range(n)]
for i in range(n):
    x = u.find(i)
    if x < 0:
        heapq.heappush(l[i],a[i])
    else:
        heapq.heappush(l[x],a[i])

h = []
for i in range(n):
    if l[i]:
        x = heapq.heappop(l[i])
        heapq.heappush(h,[x,i])
ans = 0
while len(h) > 1:
    a = heapq.heappop(h)
    b = heapq.heappop(h)
    ans += a[0]+b[0]
   
    l[a[1]] = list(heapq.merge(l[a[1]],l[b[1]]))
    
    x = heapq.heappop(l[a[1]])
    heapq.heappush(h,[x,a[1]])
print(ans)