Problem:


Score : 600 points

Problem Statement

You are given a forest with N vertices and M edges. The vertices are numbered 0 through N-1.
The edges are given in the format (x_i,y_i), which means that Vertex x_i and y_i are connected by an edge.

Each vertex i has a value a_i.
You want to add edges in the given forest so that the forest becomes connected.
To add an edge, you choose two different vertices i and j, then span an edge between i and j.
This operation costs a_i + a_j dollars, and afterward neither Vertex i nor j can be selected again.

Find the minimum total cost required to make the forest connected, or print Impossible if it is impossible.

Constraints

1 ≤ N ≤ 100,000

0 ≤ M ≤ N-1

1 ≤ a_i ≤ 10^9

0 ≤ x_i,y_i ≤ N-1

The given graph is a forest.

All input values are integers.

Input

Input is given from Standard Input in the following format:

N M
a_0 a_1 .. a_{N-1}
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the minimum total cost required to make the forest connected, or print Impossible if it is impossible.

Sample Input 1

7 5
1 2 3 4 5 6 7
3 0
4 0
1 2
1 3
5 6

Sample Output 1

7

If we connect vertices 0 and 5, the graph becomes connected, for the cost of 1 + 6 = 7 dollars.

Sample Input 2

5 0
3 1 4 1 5

Sample Output 2

Impossible

We can't make the graph connected.

Sample Input 3

1 0
5

Sample Output 3

0

The graph is already connected, so we do not need to add any edges.



Sample input:
7 5
1 2 3 4 5 6 7
3 0
4 0
1 2
1 3
5 6


Sample output:
7

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify, heappop, merge, heapreplace


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def get_dq2(buf, queue):
    dq2 = queue[0]
    while len(dq2) == 1 and len(queue) > 1:
        buf.append(heappop(queue))
        dq2 = queue[0]
    return dq2


def solve(aa, uft):
    roots = {x: [] for x, r in enumerate(uft.table) if r < 0}
    if n < (len(roots) - 1) * 2:
        return 'Impossible'
    for x, a in enumerate(aa):
        roots[uft._root(x)].append(a)
    queue = []
    for l in roots.values():
        l.sort()
        queue.append(deque(l))
    heapify(queue)
    ans = 0
    while len(queue) > 1:
        # print(queue)
        dq1 = heappop(queue)
        dq2 = queue[0]
        if len(dq1) == 1:
            buf = deque([dq1])
            while buf:
                if len(queue) == 1:
                    ans += buf[0][0] + dq2[0]
                    break
                dq2 = get_dq2(buf, queue)
                for _ in range(min(len(buf), len(dq2) - 1)):
                    ans += buf.popleft()[0] + dq2.popleft()
            heapreplace(queue, dq2)
        else:
            ans += dq1.popleft() + dq2.popleft()
            heapreplace(queue, deque(merge(dq1, dq2)))
    return ans


n, m = map(int, input().split())
aa = list(map(int, input().split()))
uft = UnionFind(n)
for _ in range(m):
    uft.union(*map(int, input().split()))
print(solve(aa, uft))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify, nsmallest

N, M = map(int, input().split())
costs = [[x] for x in list(map(int, input().split()))]
for i in range(N):
  heapify(costs[i])

# union-find
parent = list(range(N))
rank = [0] * (N)

def getRoot(x):
  if parent[x] == x:
    return x
  else:
    # ルートに繋ぎ変える
    parent[x] = getRoot(parent[x])
    return parent[x]

def unite(x, y, pop=True):
  global costs
  xRoot = getRoot(x)
  yRoot = getRoot(y)
  if xRoot == yRoot:
    print('error!')
    exit()
  #print(costs, xRoot, yRoot)
  cost = costs[xRoot][0] + costs[yRoot][0]
  if pop:
    heappop(costs[xRoot])
    heappop(costs[yRoot])
  if rank[xRoot] < rank[yRoot]:
    parent[xRoot] = yRoot
    costs[yRoot] += costs[xRoot]
    heapify(costs[yRoot])
    return cost, yRoot
  else:
    parent[yRoot] = xRoot
    costs[xRoot] += costs[yRoot]
    heapify(costs[xRoot])
    if rank[xRoot] == rank[yRoot]:
      rank[xRoot] += 1
    return cost, xRoot

for i in range(M):
  x, y = map(int, input().split())
  unite(x, y, False)

forestheap = []
singles = []
for i in range(N):
  if parent[i] == i:
    if len(costs[i]) == 1:
      # 単独ノードは、最後に判定
      singles.append(costs[i][0])
    else:
      heappush(forestheap, (costs[i][0], i))

ans = 0
while len(forestheap) > 1:
  # 2ノード以上の森同士なので、必ず2個以上使えるノードは残る
  c1, v1 = heappop(forestheap)
  c2, v2 = heappop(forestheap)
  cost, newRoot = unite(v1, v2)
  ans += cost
  heappush(forestheap, (costs[newRoot][0], newRoot))

# 単独ノードの個数よりも多くのノードが残っていればOK
if len(forestheap) == 0 or len(costs[forestheap[0][1]]) < len(singles):
  print('Impossible')
else:
  print(
    ans +
    sum(singles) +
    sum(nsmallest(len(singles), costs[forestheap[0][1]]))
  )

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())

a = map(int, raw_input().split())

x=[]
y=[]
for i in range(m):
   x0, y0 =map(int, raw_input().split())
   x.append(x0)
   y.append(y0)

g=[-1]*n

for i in range(m):
   if (g[x[i]]==-1 and g[y[i]]==-1 ):
      g[x[i]]=x[i]
      g[y[i]]=x[i]
   if (g[x[i]]==-1 and g[y[i]]<>-1 ):
      g[x[i]]=g[y[i]]
   if (g[x[i]]<>-1 and g[y[i]]==-1 ):
      g[y[i]]=g[x[i]]
   if (g[x[i]]<>-1 and g[y[i]]<>-1 ):
      b=g[x[i]]
      c=g[y[i]]
      for j in range(m):
         if g[j]==b : g[j]=c
     
f=set(g)
e=[]
for d in f:
   e.append(d)

if (len(f)==2):
   r=[]
   s=[]
   for j in range(n):
      if g[j]==e[1] : s.append(j)
      if g[j]==e[0] : r.append(j)
   if ((e[0]==-1 and len(r)>1) or (e[1]==-1 and len(s)>1)):
      print "Impossible"
   else:
      minc=a[r[0]]+a[s[0]]
      for j in r:
         for k in s:
            if minc>a[j]+a[k] :minc=a[j]+a[k]
      print minc
         
else:
   if (len(f)>2):
      print "Impossible"
   else:
      if e[0]==-1:
         r=[]
         for j in range(n):
            if g[j]==e[0] : r.append(j)

         if len(r)==2:
            print a[r[0]]+a[r[1]]
         else:
            print "Impossible"

      else:
         print 0

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
import heapq
n, m = map(int, input().split())
costs = list(enumerate(list(map(int, input().split()))))
que = deque(range(n))
vortexs = [[] for i in range(n)]
if n == 1:
    print("0")
    exit()
for i in range(m):
    l, r = map(int, input().split())
    vortexs[r].append(l)
    vortexs[l].append(r)
trees = []
def dfs(now, li, queue = deque()):
    if not li:
        li = []
    if now in que:
        que.remove(now)
        li.append(costs[now])
        for j in vortexs[now]:
            if j in que:
                queue.append(j)
        while queue:
            dfs(queue.popleft(), li, queue)
        return sorted(li, key=lambda x: x[1])
for i in range(n):
    if i in que:
        trees.append(dfs(i, []))
ans = 0
if len(trees) == 1:
    print("0")
for i in range(len(trees) - 1):
    if len(trees[i]) == 1:
        print("Impossible")
        exit()
    ans += trees[i][0][1]
    ans += trees[i + 1][0][1]
    trees[i].pop(0)
    trees[i + 1].pop(0)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque
import heapq
n, m = map(int, input().split())
costs = list(enumerate(list(map(int, input().split()))))
que = deque(range(n))
vortexs = [[] for i in range(n)]
if n == 1:
    print("0")
    exit()
for i in range(m):
    l, r = map(int, input().split())
    vortexs[r].append(l)
    vortexs[l].append(r)
trees = []
def dfs(now, li, queue = deque()):
    if not li:
        li = []
    if now in que:
        que.remove(now)
        li.append(costs[now])
        for j in vortexs[now]:
            if j in que:
                queue.append(j)
        while queue:
            dfs(queue.popleft(), li, queue)
        return sorted(li, key=lambda x: x[1])
for i in range(n):
    if i in que:
        trees.append(dfs(i, []))
ans = 0
for i in range(len(trees)):
    ans += trees[i][0][1]
    if len(trees[i]) == 1:
        print("Impossible")
        exit()
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split(' '))
A=[]
Q=list(map(int,input().split(' ')))
q=0
while q<N:
    A.append([0,0,0])
    A[q][1]=Q[q]
    A[q][2]=q
    q+=1
m=1
while m < M+1:
    x,y=map(int,input().split(' '))
    if A[x][0]==0 and A[y][0]==0:
        A[x][0]=m
        A[y][0]=m
        m+=1
    elif A[x][0]!=0 and A[y][0]!=0:
        i=0
        Ma=max(A[x][0],A[y][0])
        Ac=A.copy()
        Ac.sort()
        while i<N:
            if Ac[i][0]>Ma:
                break
            if Ac[i][0] == Ma:
                q=Ac[i][2]
                A[q][0]=Ma
            i+=1
        m += 1
    else:
        A[x][0]=max(A[x][0],A[y][0])
        A[y][0]=max(A[x][0],A[y][0])
        m+=1
A.sort()
if N==1 or (N==2 and M!=1):
    print('0')
elif N==2:
    if M==0:
        print(str(A[0][1]+A[1][1]))
elif A[1][0]==0:
    print('Impossible')
else:
    p=1
    pcount=0
    tot=0
    tot2=0
    while p < N:
        if A[p-1][0]==0 and p==1:
            tot+=A[p-1][1]
        elif p==1:
            tot+=A[p-1][1]+A[p][1]
        if A[p-1][0]!=A[p][0]:
            tot+=A[p][1]+A[p+1][1]
            pcount+=1
            tot2=A[p][1]+A[0][1]
        p+=1
    if pcount < 2:
        print(tot2)
    else:
        print(tot)

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())

a = map(int, raw_input().split())

x=[]
y=[]
for i in range(m):
   x0, y0 =map(int, raw_input().split())
   x.append(x0)
   y.append(y0)

g=[-1]*n

for i in range(m):
   if (g[x[i]]==-1 and g[y[i]]==-1 ):
      g[x[i]]=x[i]
      g[y[i]]=x[i]
   if (g[x[i]]==-1 and g[y[i]]<>-1 ):
      g[x[i]]=g[y[i]]
   if (g[x[i]]<>-1 and g[y[i]]==-1 ):
      g[y[i]]=g[x[i]]
   if (g[x[i]]<>-1 and g[y[i]]<>-1 ):
      b=g[x[i]]
      c=g[y[i]]
      for j in range(m):
         if g[j]==b : g[j]=c
     
f=set(g)
if (len(f)==2):
   e=[]
   for d in f:
      e.append(d)
   r=[]
   s=[]
   for j in range(n):
      if g[j]==e[1] : s.append(j)
      if g[j]==e[0] : r.append(j)
   if ((e[0]==-1 and len(r)>1) or (e[1]==-1 and len(s)>1)):
      print "Impossible"
   else:
      minc=a[r[0]]+a[s[0]]
      for j in r:
         for k in s:
            if minc>a[j]+a[k] :minc=a[j]+a[k]
      print minc
         
else:
   print "Impossible"

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split(' '))
A=[]
Q=list(map(int,input().split(' ')))
q=0
while q<N:
    A.append([0,0,0])
    A[q][1]=Q[q]
    A[q][2]=q
    q+=1
m=1
while m < M+1:
    x,y=map(int,input().split(' '))
    if A[x][0]==0 and A[y][0]==0:
        A[x][0]=m
        A[y][0]=m
        m+=1
    elif A[x][0]!=0 and A[y][0]!=0:
        i=0
        Ma=max(A[x][0],A[y][0])
        Ac=A.copy()
        Ac.sort()
        while i<N:
            if Ac[i][0]>Ma:
                break
            if Ac[i][0] == Ma:
                q=Ac[i][2]
                A[q][0]=Ma
            i+=1
        m += 1
    else:
        A[x][0]=max(A[x][0],A[y][0])
        A[y][0]=max(A[x][0],A[y][0])
        m+=1
A.sort()
print(A)
if N==1 or (N==2 and M!=1):
    print('0')
elif N==2:
    if M==0:
        print(str(A[0][1]+A[1][1]))
elif A[1][0]==0:
    print('Impossible')
else:
    p=1
    pcount=0
    tot=0
    tot2=0
    while p < N:
        if A[p-1][0]==0 and p==1:
            tot+=A[p-1][1]
        elif p==1:
            tot+=A[p-1][1]+A[p][1]
        if A[p-1][0]!=A[p][0]:
            tot+=A[p][1]+A[p+1][1]
            pcount+=1
            tot2=A[p][1]+A[0][1]
        p+=1
    if pcount < 2:
        print(tot2)
    else:
        print(tot)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify

N, M = map(int, input().split())
costs = [[x] for x in list(map(int, input().split()))]
for i in range(N):
  heapify(costs[i])

# union-find
parent = list(range(N))
rank = [0] * (N)

def getRoot(x):
  if parent[x] == x:
    return x
  else:
    # ルートに繋ぎ変える
    parent[x] = getRoot(parent[x])
    return parent[x]

def unite(x, y, pop=True):
  global costs
  xRoot = getRoot(x)
  yRoot = getRoot(y)
  if xRoot == yRoot:
    print('error!')
    exit()
  #print(costs, xRoot, yRoot)
  cost = costs[xRoot][0] + costs[yRoot][0]
  if pop:
    heappop(costs[xRoot])
    heappop(costs[yRoot])
  if rank[xRoot] < rank[yRoot]:
    parent[xRoot] = yRoot
    costs[yRoot] += costs[xRoot]
    heapify(costs[yRoot])
    return cost, yRoot
  else:
    parent[yRoot] = xRoot
    costs[xRoot] += costs[yRoot]
    heapify(costs[xRoot])
    if rank[xRoot] == rank[yRoot]:
      rank[xRoot] += 1
    return cost, xRoot

for i in range(M):
  x, y = map(int, input().split())
  unite(x, y, False)

forestheap = []
for i in range(N):
  if parent[i] == i:
    heappush(forestheap, (costs[i][0], i))

ans = 0
while len(forestheap) > 1:
  c1, v1 = heappop(forestheap)
  c2, v2 = heappop(forestheap)
  cost, newRoot = unite(v1, v2)
  ans += cost
  # 使えるノードがなくなって、まだ連結でなければ失敗
  if len(costs[newRoot]) == 0:
    print('Impossible')
    exit()
  heappush(forestheap, (costs[newRoot][0], newRoot))

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())

a = map(int, raw_input().split())

x=[]
y=[]
for i in range(m):
   x0, y0 =map(int, raw_input().split())
   x.append(x0)
   y.append(y0)

g=[-1]*n

for i in range(m):
   if (g[x[i]]==-1 and g[y[i]]==-1 ):
      g[x[i]]=x[i]
      g[y[i]]=x[i]
   if (g[x[i]]==-1 and g[y[i]]<>-1 ):
      g[x[i]]=g[y[i]]
   if (g[x[i]]<>-1 and g[y[i]]==-1 ):
      g[y[i]]=g[x[i]]
   if (g[x[i]]<>-1 and g[y[i]]<>-1 ):
      b=g[x[i]]
      c=g[y[i]]
      for j in range(m):
         if g[j]==b : g[j]=c
     
f=set(g)
if (len(f)==2):
   e=[]
   for d in f:
      e.append(d)
   r=[]
   s=[]
   for j in range(n):
      if g[j]==e[1] : s.append(j)
      if g[j]==e[0] : r.append(j)

   minc=a[r[0]]+a[s[0]]
   for j in r:
      for k in s:
         if minc>a[j]+a[k] :minc=a[j]+a[k]
   print minc
         
else:
   print "Impossible"

Submission status: Wrong Answer

Solution code:
# D
import numpy as np

N, M = map(int, input().split())
a_list = list(map(int, input().split()))

G = dict()
for i in range(N):
    G[i] = []

for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
    
res = 0
connec = 0
done_list = [0]*N
conn_list = []

st = 0
while True:
    while st < N:
        if done_list[st] == 0:
            break
        st += 1

    if st == N:
        break

    queue = [st]
    conn = [a_list[st]]
    conn_ = [st]
    done_list[st] = 1
    connec += 1

    while len(queue) > 0:
        s = queue.pop()
        for t in G[s]:
            if done_list[t] == 0:
                done_list[t] = 1
                queue.append(t)
                conn.append(a_list[t])
                conn_.append(t)
                
    args = np.argsort(conn)
    res += conn[args[0]]
    a_list[conn_[args[0]]] = 2000000000

a_list.sort()

if connec == 1:
    print(0)
elif len(conn_list) < connec - 2:
    print('Impossible')
else:
    print(res + sum(conn_list[:(connec - 2)]))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split(' '))
A=[]
Q=list(map(int,input().split(' ')))
q=0
while q<N:
    A.append([0,0])
    A[q][1]=Q[q]
    q+=1
m=1
while m < M+1:
    x,y=map(int,input().split(' '))
    if A[x][0]==0 and A[y][0]==0:
        A[x][0]=m
        A[y][0]=m
        m+=1
    elif A[x][0]!=0 and A[y][0]!=0:
        i=0
        Ma=max(A[x][0],A[y][0])
        while i<N:
            if A[i][0] == Ma:
                A[i][0] = min(A[x][0],A[y][0])
            i+=1
        m += 1
    else:
        A[x][0]=max(A[x][0],A[y][0])
        A[y][0]=max(A[x][0],A[y][0])
        m+=1
A.sort()
if N==1 or (N==2 and M!=1):
    print('0')
elif N==2:
    if M==0:
        print(str(A[1][0]+A[1][1]))
elif A[1][0]==0:
    print('Impossible')
else:
    p=1
    pcount=0
    tot=0
    tot2=0
    while p < N:
        if A[p-1][0]==0 and p==1:
            tot+=A[p-1][1]
        elif p==1:
            tot+=A[p-1][1]+A[p][1]
        if A[p-1][0]!=A[p][0]:
            tot+=A[p][1]+A[p+1][1]
            pcount+=1
            tot2=A[p][1]+A[0][1]
        p+=1
    if pcount < 2:
        print(tot2)
    else:
        print(tot)

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import defaultdict

N,M=map(int, raw_input().split())
if M==0:
	if N==1:
		print 0
		quit()
	else:
		print "Impossible"
		quit()

cost=map(int, raw_input().split())

nl=[ [] for i in range(N) ]


for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)


d=[ None for i in range(N) ]
V=[ None for i in range(N) ]

def dfs(start):
	q = deque([]) 
	V[start]=start
	d[start]=0
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i] is None:
				V[i]=start
				q.append(i)

while None in V:
	i=V.index(None)
	dfs(i)

group=defaultdict(lambda: float("inf"))

for i,j in zip(cost,V):
	group[j]=min(group[j], i)


group_cnt=len(group.values())
min_val=min(group.values())

print sum( group.values() )+ ( group_cnt-2 )* min_val

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

class UnionFind(object):

    def __init__(self):
        self.table = defaultdict(lambda:-1)

    def find(self, x):
        parent = self.table[x] 
        if parent < 0:
            return x
        else:
            root = self.find(parent)
            self.table[x] = root
            return root

    def union(self, x1, x2):
        root1 = self.find(x1)
        root2 = self.find(x2)
        if root1 < root2:
            self.table[root1] += self.table[root2]
            self.table[root2] = root1
        else:
            self.table[root2] += self.table[root1]
            self.table[root1] = root2

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
xy = [[int(x) for x in input().split()] for i in range(M)]

def solve(N, M, A, xy):

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

    groups = defaultdict(list)
    for i in range(N):
        groups[uf.find(i)].append(A[i])

    groups = [sorted(g, reverse=True) for g in groups.values()]

    r = 0
    while 1:
        if len(groups) < 2:
            break
        groups.sort(key=lambda x:x[-1])
        # print(groups)
        w = groups.pop()
        w0 = groups[0]
        r += w0.pop() + w.pop()
        w0 += w
        w0.sort(reverse=True)
        if len(w0) == 0 and len(groups) >= 1:
            return "Impossible"

    return r

print(solve(N, M, A, xy))

Submission status: Wrong Answer

Solution code:
class DisjointSet:
  def __init__(self, size):
    self.parent = list(range(size))
    self.rank = [0]*size
  
  def find(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find(self.parent[x])
      return self.parent[x]

  def union(self, x, y):
    xr, yr = self.find(x), self.find(y)
    
    if self.rank[xr] > self.rank[yr]:
      self.parent[yr] = xr
    elif self.rank[xr] < self.rank[yr]:
      self.parent[xr] = yr
    elif xr != yr:
      self.parent[yr] = xr
      self.rank[xr] += 1


from sys import stdin
import heapq as hq

N,M = map(int,stdin.readline().split())
if (N-1-M)*2 > N:
  print('Impossible')
  exit()


A = tuple(map(int,stdin.readline().split()))

ds = DisjointSet(N)
lines = stdin.readlines()
for line in lines:
  x,y = map(int,line.split())
  ds.union(x,y)

Q = [[] for _ in range(N)]

for i,a in enumerate(A):
  Q[ds.find(i)].append(a)

del ds
for t in Q:
  hq.heapify(t)

Q = [t for t in Q if t]

hq.heapify(Q)

cost = 0

while len(Q) > 1:
  a = hq.heappop(Q)
  b = hq.heappop(Q)
  cost += a[0]+b[0]
  hq.heappop(a)
  hq.heappop(b)
  a += b
  if a:
    hq.heapify(a)
    hq.heappush(Q,a)

print(cost)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify, heappop, merge, heapreplace, heappush


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def solve(aa, uft):
    roots = {x: [] for x, r in enumerate(uft.table) if r < 0}
    if n < (len(roots) - 1) * 2:
        return 'Impossible'
    for x, a in enumerate(aa):
        roots[uft._root(x)].append(a)
    queue = []
    for l in roots.values():
        l.sort()
        queue.append(deque(l))
    heapify(queue)
    ans = 0
    while len(queue) > 1:
        buf = []
        dq1 = heappop(queue)
        dq2 = queue[0]
        if len(dq1) == 1:
            while len(dq2) == 1 and len(queue) > 1:
                buf.append(heappop(queue))
                dq2 = queue[0]
        ans += dq1.popleft() + dq2.popleft()
        heapreplace(queue, deque(merge(dq1, dq2)))
        for b in buf:
            heappush(queue, b)
    return ans


n, m = map(int, input().split())
aa = list(map(int, input().split()))
uft = UnionFind(n)
for _ in range(m):
    uft.union(*map(int, input().split()))
print(solve(aa, uft))

Submission status: Wrong Answer

Solution code:
# D
N, M = map(int, input().split())
a_list = list(map(int, input().split()))

G = dict()
for i in range(N):
    G[i] = []

for _ in range(M):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)
    
res = 0
connec = 0
done_list = [0]*N
conn_list = []

s = 0
while True:
    while s < N:
        if done_list[s] == 0:
            break
        s += 1

    if s == N:
        break

    queue = [s]
    conn = [a_list[s]]
    done_list[s] = 1
    connec += 1

    while len(queue) > 0:
        s = queue.pop()
        for t in G[s]:
            if done_list[t] == 0:
                done_list[t] = 1
                queue.append(t)
                conn.append(a_list[t])
                
    conn_ = sorted(conn, reverse=True)
    res += conn_.pop()
    conn_list = conn_list + conn_

conn_list_ = sorted(conn_list)

if connec == 1:
    print(0)
elif len(conn_list_) < connec - 2:
    print('Impossible')
else:
    print(res + sum(conn_list_[:(connec - 2)]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

class UnionFind(object):

    def __init__(self):
        self.table = defaultdict(lambda:-1)

    def find(self, x):
        parent = self.table[x] 
        if parent < 0:
            return x
        else:
            root = self.find(parent)
            self.table[x] = root
            return root

    def union(self, x1, x2):
        root1 = self.find(x1)
        root2 = self.find(x2)
        if root1 < root2:
            self.table[root1] += self.table[root2]
            self.table[root2] = root1
        else:
            self.table[root2] += self.table[root1]
            self.table[root1] = root2

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
xy = [[int(x) for x in input().split()] for i in range(M)]

def solve(N, M, A, xy):

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

    groups = defaultdict(list)
    for i in range(N):
        groups[uf.find(i)].append(A[i])

    groups = [sorted(g, reverse=True) for g in groups.values()]

    r = 0
    while 1:
        groups.sort(key=lambda x:x[-1], reverse=True)
        # print(groups)
        if len(groups) < 2:
            break
        w1 = groups.pop()
        w2 = groups.pop()
        r += w1.pop() + w2.pop()
        w2 += w1
        w2.sort(reverse=True)
        if len(w2) == 0 and len(groups) >= 1:
            return "Impossible"
        groups.append(w2)

    return r

print(solve(N, M, A, xy))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
a = list(map(int, input().split()))
xy=[list(map(int,input().split())) for i in range(m)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, 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 = 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):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, 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())

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

g=uf.group_count()

if g==1:
    print(0)
    exit()

if n<(g-1)*2:
    print("Impossible")
    exit()

ans=0

all_costs=[]
for r in uf.roots():
    costs=[]
    for mem in uf.members(r):
        costs.append(a[mem])
    costs.sort()
    ans+=costs[0]
    all_costs.extend(costs[1:])

all_costs.sort()
ans+=sum(all_costs[:(g-2)])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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()}

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

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 in uf.roots():
    tmp, i = min((A[x], x) for x in uf.members(root))
    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)

Submission status: Time Limit Exceeded

Solution code:
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()}

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

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 = []
for root in uf.roots():
    tmp, i = min((A[x], x) for x in uf.members(root))
    used.append(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)