Problem p03440 (python)

Fixed submission:
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  ri = root(R, i)
  rj = root(R, j)
  if ri <= rj:
    R[rj] = ri
  else:
    R[ri] = rj
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  R[i] = root(R, i)
if N < 2 * (N - M - 1):
  print('Impossible')
elif M == N - 1:
  print(0)
else:
  cnt= 0
  E = N - M - 2
  C = [0] * N
  F = sorted([[a, R[i]] for i, a in enumerate(A)])
  for a, r in F:
    if C[r] == 0:
      C[r] = a
      cnt += a
    elif E > 0:
      cnt += a
      E -= 1
  print(cnt)

Buggy submission (verdict: Runtime Error):
import heapq
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  Ri = root(R, i)
  Rj = root(R, j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(R, i)
T = {}
for i, t in enumerate(list(set(R))):
  T[t] = i
F = [[] for i in T]
for i, r in enumerate(R):
  heapq.heappush(F[T[r]], A[i])
F = [sorted(f) for f in F]
RF = [i for i in range(len(F))]
ans = 0
LF = len(F)
for i in range(LF - 1):
  for f in F:
    if len(list(f)) == 0:
      ans = 'Impossible'
  if ans == 'Impossible':
    break
  f0 = sorted([[heapq.heappop(f), j] for j, f in enumerate(F)])
  ans += f0[0][0] + f0[1][0]
  for f in f0[2:]:
    heapq.heappush(F[f[1]], f[0])
  F[f0[0][1]] = heapq.heapify(list(heapq.merge(F[f0[0][1]], F[f0[1][1]])))
  F.pop(f0[1][1])
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  Ri = root(R, i)
  Rj = root(R, j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(R, i)
T = {}
for i, t in enumerate(list(set(R))):
  T[t] = i
F = [[] for i in T]
for i, r in enumerate(R):
  heapq.heappush(F[T[r]], A[i])
F = [sorted(f) for f in F]
RF = [i for i in range(len(F))]
ans = 0
if len(F) > 1:
  for i in range(len(F) - 1):
    for f in F:
      if len(list(f)) == 0:
        ans = 'Impossible'
    if ans == 'Impossible':
      break
    f0 = sorted([[heapq.heappop(F[j]), j] for j in range(len(F))])
    ans += f0[0][0] + f0[1][0]
    for f in f0[2:]:
      heapq.heappush(F[f[1]], f[0])
    F[f0[0][1]] = heapq.merge(F[f0[0][1]], F[f0[1][1]])
    F.pop(f0[1][1])
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  Ri = root(R, i)
  Rj = root(R, j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(R, i)
T = {}
for i, t in enumerate(list(set(R))):
  T[t] = i
F = [[] for i in T]
for i, r in enumerate(R):
  heapq.heappush(F[T[r]], A[i])
F = [sorted(f) for f in F]
RF = [i for i in range(len(F))]
ans = 0
if len(F) > 1:
  for i in range(len(F) - 1):
    for f in F:
      if len(f) == 0:
        ans = 'Impossible'
    if ans == 'Impossible':
      break
    f0 = sorted([[heapq.heappop(F[j]), j] for j in range(len(F))])
    ans += f0[0][0] + f0[1][0]
    for f in f0[2:]:
      heapq.heappush(F[f[1]], f[0])
    F[f0[0][1]] = heapq.merge(F[f0[0][1]], F[f0[1][1]])
    F.pop(f0[1][1])
print(ans)

Buggy submission (verdict: Runtime Error):
import heapq
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(R, i):
  if R[i] == i:
    return i
  else:
    R[i] = root(R, R[i])
    return R[i]
def union(i, j):
  Ri = root(R, i)
  Rj = root(R, j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(R, i)
T = {}
for i, t in enumerate(list(set(R))):
  T[t] = i
F = [[] for i in T]
for i, r in enumerate(R):
  heapq.heappush(F[T[r]], A[i])
F = [sorted(f) for f in F]
RF = [i for i in range(len(F))]
ans = 0
if len(F) > 1:
  for i in range(len(F) - 1):
    for f in enumerate(F):
      if len(f) == 0:
        ans = 'Impossible'
    if ans == 'Impossible':
      break
    f0 = sorted([[heapq.heappop(F[j]), j] for j in range(len(F))])
    ans += f0[0][0] + f0[1][0]
    for f in f0[2:]:
      heapq.heappush(F[f[1]], f[0])
    F[f0[0][1]] = heapq.merge(F[f0[0][1]], F[f0[1][1]])
    F.pop(f0[1][1])
print(ans)

Buggy submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = [int(x) for x in input().split()]
R = [i for i in range(N)]
def root(i):
  if R[i] == A[i]:
    return A[i]
  else:
    R[i] = root(R[i])
    return R[i]
def union(i, j):
  Ri = root(i)
  Rj = root(j)
  if A[Ri] <= A[Rj]:
    R[j] = i
  else:
    R[i] = j
for m in range(M):
  i, j = map(int, input().split())
  union(i, j)
for i in range(N):
  r = root(i)
F = sorted([A[i] for i in list(set(R))])
ans = 0
for a in A[1:]:
  ans += A[0] + a
print(ans)