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: Accepted

Solution code:
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 same(self, x, y):
    return self.find(x) == self.find(y)

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
from bisect import *
from collections import defaultdict
def solve():
  ans = 0
  N, M = map(int, input().split())
  A = list(map(int, input().split()))
  uf = UnionFind(N)
  for _ in range(M):
    x,y = map(int, input().split())
    uf.union(x,y)
  if N>2*(M+1):
    return 'Impossible'
  if N-M==1:
    return 0
  d = defaultdict(lambda: [])
  for i in range(N):
    r = uf.find(i)
    if r<0:
      d[i].append(A[i])
    else:
      d[r].append(A[i])
  lis1 = []
  for v in d.values():
    mini = min(v)
    ans += mini
    v.remove(mini)
    for l in v:
      insort_right(lis1,l)
  ans += sum(lis1[:(N-M-2)])
  return ans
print(solve())

Submission status: Accepted

Solution code:
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

    def find(self, x):
        if self.uf[x]<0: return x
        self.uf[x] = self.find(self.uf[x])
        return self.uf[x]

    def size(self, x):
        return -self.uf[self.find(x)]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1
        
N, M = map(int, input().split())
A = list(map(int, input().split()))
uf = UF(N)
for _ in range(M):
    x, y = map(int, input().split())
    uf.union(x,y)

D = {}
for x, a in enumerate(A):
    c = uf.find(x)
    if c not in D: D[c]=[]
    D[c].append(a)

ans = 0
L = []
for d in D.values():
    d.sort()
    ans += d[0]
    L += d[1:]

L.sort()

P = len(D)-2
if len(D)==1:
    ans = 0
elif len(L)>=P:
    ans += sum(L[:len(D)-2])
else:
    ans = 'Impossible'

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
import heapq

n, m = map(int, input().split())
if m == n-1:
  print(0)
  exit()
if n < 2*(n-m-1):
  print("Impossible")
  exit()
A = tuple(map(int, input().split()))
G = [[] for _ in range(n)]
for _ in range(m):
  x, y = map(int, input().split())
  G[x].append(y)
  G[y].append(x)
ans = 0
L = []
seen = [False]*n
def dfs(v):
  global ans
  K = []
  stack = [v]
  while stack:
    v = stack.pop()
    heapq.heappush(K, A[v])
    seen[v] = True
    for nv in G[v]:
      if seen[nv]:
        continue
      stack.append(nv)
  ans += heapq.heappop(K)
  for k in K:
    heapq.heappush(L, k)
for i in range(n):
  if not seen[i]:
    dfs(i)
for _ in range(n-m-2):
  ans += heapq.heappop(L)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
xy = list(map(int,read().split()))

if(n-m==1):
    print(0)
    exit()

p = ((n-1)-m)*2
if( p > n):
    print('Impossible')
    exit()

sys.setrecursionlimit(10**9)

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

    def find(self,x):
        if(self.parents[x] < 0):
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

    def same(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        return (x_root == y_root)

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def members(self,x):
        root = self.find(x)
        ret = [ i for i in range(self.n) if self.find(i) == root ]
        return ret

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(n)
hqs = [[] for _ in range(n)]

it = iter(xy)
for x,y in zip(it,it):
    uf.union(x,y)

for i in range(n):
    root = uf.find(i)
    heappush(hqs[root], a[i])

ans = []
others = []
for i in range(n):
    if(hqs[i]):
        ans.append(heappop(hqs[i]))
        # others += hqs[i]
        others.extend(hqs[i])

others.sort()
rem = p - len(ans)
# ans += others[:rem]
ans.extend(others[:rem])

print(sum(ans))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
xy = list(map(int,read().split()))

if(n-m==1):
    print(0)
    exit()

p = ((n-1)-m)*2
if( p > n):
    print('Impossible')
    exit()

sys.setrecursionlimit(10**9)

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

    def find(self,x):
        if(self.parents[x] < 0):
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

    def same(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        return (x_root == y_root)

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def members(self,x):
        root = self.find(x)
        ret = [ i for i in range(self.n) if self.find(i) == root ]
        return ret

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(n)
hqs = [[] for _ in range(n)]

it = iter(xy)
for x,y in zip(it,it):
    uf.union(x,y)

for i in range(n):
    root = uf.find(i)
    heappush(hqs[root], a[i])

ans = []
others = []
for i in range(n):
    if(hqs[i]):
        ans.append(heappop(hqs[i]))
        others += hqs[i]

others.sort()
rem = p - len(ans)
ans += others[:rem]

print(sum(ans))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
xy = list(map(int,read().split()))

if(n-m==1):
    print(0)
    exit()

p = ((n-1)-m)*2
if( p > n):
    print('Impossible')
    exit()

sys.setrecursionlimit(10**9)

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

    def find(self,x):
        if(self.parents[x] < 0):
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def size(self, x):
        return self.parents[ self.find(x) ] * -1

    def same(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        return (x_root == y_root)

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x_root == y_root):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def members(self,x):
        root = self.find(x)
        ret = [ i for i in range(self.n) if self.find(i) == root ]
        return ret

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(n)
hqs = [[] for _ in range(n)]

it = iter(xy)
for x,y in zip(it,it):
    uf.union(x,y)

for i in range(n):
    root = uf.find(i)
    heappush(hqs[root], a[i])

ans = []
others = []
for i in range(n):
    if(hqs[i]):
        ans.append(heappop(hqs[i]))
        for j in hqs[i]:
            others.append(j)

others.sort()
rem = p - len(ans)
ans = ans + others[:rem]

print(sum(ans))

Submission status: Accepted

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

a=list(map(int,input().split()))

union=[-1]*n

tree=[[] for _ in range(n)]
for _ in range(m):
    x,y=map(int,input().split())
    tree[x].append(y)
    tree[y].append(x)

cnt=-1
for i in range(n):
    if union[i]==-1:
        stack=[i]
        cnt+=1
        while len(stack)>0:
            tmp=stack.pop()
            union[tmp]=cnt
            for item in tree[tmp]:
                if union[item]==-1:
                    union[item]=cnt
                    stack.append(item)

if cnt==0:
    print(0)
    exit()

cost=[[] for _ in range(cnt+1)]
#print(union)
for i,aa in enumerate(a):
    cost[union[i]].append(aa)

import heapq

del_list=[]
kouho_list=[]

ans=0

#print(cost)
for i in range(cnt+1):
    tmp=min(cost[i])
    ans+=tmp
    del_list.append(tmp)
    kouho_list+=cost[i]
    #print(cost)

#print(cost)
heapq.heapify(kouho_list)
heapq.heapify(del_list)

for _ in range(2*(n-m-1)-(cnt+1)):
    #print(kouho_list,del_list)
    while 1:
        #print(kouho_list,del_list)
        if len(kouho_list)>0:
            tmp=heapq.heappop(kouho_list)
        else:
            print("Impossible")
            exit()
        
        if len(del_list)>0:
            if del_list[0]!=tmp:
                break
            else:
                heapq.heappop(del_list)
        else:
            break
        
    ans+=tmp

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        '''
        ルートのノードを見つける
        '''
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        '''
        ノード同士を連結する
        '''
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]


from heapq import heappop, heappush, heapify

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    union = UnionFind(N)
    for i in range(M):
        x, y = map(int, input().split())
        union.unite(x, y)
    select_node = 2 * (N- M - 1)
    if select_node > N:
        print("Impossible")
        return
    if N - 1 == M:
        print(0)
        return
    node = [0] * N
    qtable = [[] for _ in range(N)]
    allq = []
    for i in range(N):
        node[i] = union.find_root(i)
        heappush(qtable[node[i]], A[i])
    ans = 0
    cnt = 0
    for i in range(N):
        if qtable[i]:
            ans += heappop(qtable[i])
            cnt += 1
        allq.extend(qtable[i])

    heapify(allq)
    for i in range(select_node-cnt):
        ans += heappop(allq)
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

def main():
    n, m = getList()
    uf = UnionFind(n)
    costs = getList()

    q = []
    for i, c in enumerate(costs):
        heapq.heappush(q, (c, i))
    # print(q)
    hen = 0
    for _ in range(m):
        a, b = getList()
        if not uf.same_check(a, b):
            uf.union(a,b)
            hen += 1
 
    # print(uf.par)
    ans = 0
    used = defaultdict(int)
    kaburi = []
    mc = 0
    while(q):
        c1, m1 = heapq.heappop(q)
        if uf.find(m1) not in used.keys():
            ans += c1
            used[uf.find(m1)] = 1
            mc += 1
        else:
            heapq.heappush(kaburi, (c1, m1))

    # print(kaburi, hen, ans)
    if mc == 1:
        print(0)
        return 

    if len(kaburi) >= 2 * (n - hen - 1) - mc:
        for _ in range(2 * (n - hen - 1) - mc):
            c1, m1 = heapq.heappop(kaburi)
            ans += c1
        print(ans)
        return 
    else:
        print("Impossible")
        return


if __name__ == "__main__":
    main()
    # solve()

Submission status: Accepted

Solution code:
import heapq
import itertools


class UnionFind:

    def __init__(self, size: int):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.size = size
        self.parent = [-1] * size

    def find(self, x: int) -> int:
        """
        xを含む集合の代表を求める
        """
        if self.parent[x] < 0:
            return x
        # 集合の代表にリンクを繋ぎ変える
        same_group_items = []
        while self.parent[x] >= 0:
            same_group_items.append(x)
            x = self.parent[x]
        for child in same_group_items:
            self.parent[child] = x
        return x

    def unite(self, x: int, y: int):
        """
        xを含む集合とyを含む集合を併合する
        """
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.parent[root_x] >= self.parent[root_y]:
                self.parent[root_x] += self.parent[root_y]
                self.parent[root_y] = root_x
            else:
                self.parent[root_y] += self.parent[root_x]
                self.parent[root_x] = root_y

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def count_group(self) -> int:
        """
        集合の数を数える。
        """
        count = 0
        for i in range(self.size):
            if self.parent[i] < 0:
                count += 1
        return count


n, m = map(int, input().split())
a = list(map(int, input().split()))

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


uf = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    uf.unite(x, y)

hs = [[] for i in range(n)]
for i in range(n):
    p = uf.find(i)
    heapq.heappush(hs[p], a[i])
cost = 0
for i in range(n):
    if len(hs[i]) > 0:
        cost += heapq.heappop(hs[i])
hs = list(itertools.chain.from_iterable(hs))
heapq.heapify(hs)
for i in range(uf.count_group(), 2*(n-m-1)):
    cost += heapq.heappop(hs)
print(cost)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
XY = [tuple(map(int,input().split())) for i in range(M)]

if M==N-1:
    print(0)
    exit()

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

uf = UnionFind(N)
for x,y in XY:
    if uf.is_same(x,y): continue
    uf.unite(x,y)
for i in range(N):
    uf.root(i)

from collections import defaultdict
dic = defaultdict(lambda: set())
for i in range(N):
    dic[uf.root(i)].add(i)

need = (len(dic)-1)*2
if need > N:
    print('Impossible')
    exit()

ans = used = 0
import heapq
hq = []
heapq.heapify(hq)
for r,vs in dic.items():
    mini = -1
    mina = 10**9+1
    for i in vs:
        if A[i] < mina:
            mina = A[i]
            mini = i
    ans += mina
    used += 1
    for i in vs:
        if i==mini: continue
        heapq.heappush(hq, A[i])

for _ in range(need - used):
    ans += heapq.heappop(hq)
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
if m == n-1:
  print(0)
  exit()
if 2*(n-m-1) > 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)
count = 2*(n-m-1)
l = [[] for i in range(n)]
for i in range(n):
    x = u.find(i)
    if x < 0:
        l[i].append(a[i])
    else:
        l[x].append(a[i])

ans = 0
h = []
for i in range(n):
    if l[i]:
        l[i].sort()
        ans += l[i][0]
        count -= 1
        for j in l[i][1:]:
            h.append(j)
h.sort()
ans += sum(h[:count])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
# debug = lambda *a, **kw: print(*a, **kw, file=sys.stderr)

N, M = inm()
A = inl()
assert len(A) == N


def solve():
    uf = UnionFind(N)
    for _ in range(M):
        x, y = inm()
        uf.union(x, y, pay=False)
    rs = uf.roots()
    rs.sort(key=lambda x: uf.size(x), reverse=True)
    s = rs[0]
    for i in range(1, len(rs)):
        if not uf.union(s, rs[i], pay=True):
            return "Impossible"
    return uf.paid_cost()


class UnionFind:
    def __init__(self, n):
        # total number of nodes.
        self.n = n
        # node id -> root node id
        self._root_table = list(range(n))
        # root node id -> group size
        self._size_table = [1] * n
        self._cost_table = [[A[i]] for i in range(n)]  # heaps
        self._paid_cost = 0

    def paid_cost(self):
        return self._paid_cost

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            # Update the cache on query.
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y, pay):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # Ensure that x is the larger (or equal) group.
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

        if pay:
            if not self._cost_table[x]:
                return False
            ax = heapq.heappop(self._cost_table[x])
            if not self._cost_table[y]:
                return False
            ay = heapq.heappop(self._cost_table[y])
            self._paid_cost += ax + ay

        for z in self._cost_table[y]:
            heapq.heappush(self._cost_table[x], z)
        self._cost_table[y] = []
        return True

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())


print(solve())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]


class UnionFind:#早いunionfind,親はclass[i]のように要素指定すればok
    def __init__(self, elements=None):
        """Create a new empty union-find structure.
        If *elements* is an iterable, this structure will be initialized
        with the discrete partition on the given set of elements.
        """
        if elements is None:
            elements = ()
        self.parents = {}
        self.weights = {}
        for x in elements:
            self.weights[x] = 1
            self.parents[x] = x

    def __getitem__(self, i):
        """Find and return the name of the set containing the i."""

        # check for previously unknown i
        if i not in self.parents:
            self.parents[i] = i
            self.weights[i] = 1
            return i

        # find path of is leading to the root
        path = [i]
        root = self.parents[i]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]

        # compress the path and return
        for ancestor in path:
            self.parents[ancestor] = root
        return root

    def __iter__(self):#for parent in Class:
        return iter(self.parents)

    def union(self, *objects):#union the parents of objects
        """Find the sets containing the objects and merge them all."""
        roots = [self[x] for x in objects]
        # Find the heaviest root according to its weight.
        heaviest = max(roots, key=lambda r: self.weights[r])
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest

    def __len__(self):
        return len(self.parents)


def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, M = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    tree=UnionFind(list(range(N)))
    for i in range(M):
        x,y=map(int, input().split())
        tree.union(x,y)
    d=dict()
    for i in range(N):
        root=tree[i]
        if root not in d:
            d[root]=[]
        heappush(d[root],A[i])
    nr=len(d.keys())
    if nr==1:
        print(0)
        return

    if 2*(nr-1)>N:
        print('Impossible')
        return 
    
    ans=0
    #print(d)
    ocount=0
    As=[]
    
    for j, q in d.items():
        a=heappop(q)
        ans+=a
        As+=q
    
    As.sort()
    for i in range(0,nr-2):
        ans+=As[i]
    


    print(ans)

    






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_size(self, x):
        return self.size[self.find(x)]

N, M = map(int, input().split())
a = list(map(int, input().split()))
uf = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    uf.unite(x, y)
group = defaultdict(list)
for i in range(N):
    group[uf.find(i)].append(a[i])
if len(group) == 1:
    print(0)
    exit()
ans = 0
rem = []
for k, v in group.items():
    v.sort()
    ans += v[0]
    rem += v[1:]
if len(rem) < len(group) - 2:
    print('Impossible')
else:
    rem.sort()
    ans += sum(rem[:len(group) - 2])
    print(ans)