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:
import sys

def wantp(n):

    wpq = []
    while n != p[n]:
        wpq.append(n)
        n = p[n]

    for i in wpq:
        p[i] = n

    return n


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

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


p = [i for i in range(N)]
rank = [1] * N

dic = {}

ans = 0

for i in range(M):

    x,y = map(int,input().split())

    xp = wantp(x)
    yp = wantp(y)

    if xp != yp:

        if rank[xp] < rank[yp]:
            p[xp] = yp
        elif rank[xp] > rank[yp]:
            p[yp] = xp
        else:
            p[yp] = xp
            rank[yp] += 1

for i in range(N):

    now = i
    np = wantp(now)

    if np not in dic:
        dic[np] = []

    dic[np].append(a[i])

    """

    if np not in dic:
        dic[np] = [float("inf"),float("inf"),float("inf")]

    if dic[np][1] > a[i]:
        dic[np][2] = dic[np][1]
        dic[np][1] = a[i]

    elif dic[np][2] > a[i]:
        dic[np][2] = a[i]

    if dic[np][2] == float("inf"):
        dic[np][0] = dic[np][1]
    else:
        dic[np][0] = dic[np][1] + dic[np][2]

    """



ans = 0
able = []
#print(dic)

for i in dic:
    dic[i].sort()
    ans += dic[i][0]

    for j in range(len(dic[i])-1):
        able.append(dic[i][j+1])
    

able.sort()

if len(dic) == 1:
    print (0)
    sys.exit()

elif len(dic) - 1 > N // 2:
    print ("Impossible")
    sys.exit()

for i in range(len(dic)-2):

    ans += able[i]

print (ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random  # randome is not available at Codeforces
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()
import sys
sys.setrecursionlimit(10**7)

show_flg=False
show_flg=True


n,m=LI()
a=LI()
g=[[] for _ in range(n)]
ans=0
cmp=0
for i in range(m):
    x,y=LI()
    g[x].append(y)
    g[y].append(x)

rest=[]
q=[]
v=[-1]*n

for i in range(n):
    if v[i]!=-1:
        continue
    p=[]
    cost=[]
    p.append(i)
    heappush(cost,a[i])
    while p:
        c=p.pop()
        v[c]=a[c]
        for nb in g[c]:
            if v[nb]==-1:
                p.append(nb)
                v[nb]=a[nb]
                heappush(cost,a[nb])
    ans+=heappop(cost)
    cmp+=1
    while cost:
        heappush(rest,heappop(cost))

if cmp==1:
    ans=0
elif len(rest)<cmp-2:
    ans="Impossible"
else:# cmp=n-m, n-m-1 edges needed, 2n-2m-2 vers, 2n-2m-2-cmp=n-m-2=cmp-2
    for i in range(cmp-2):
        ans+=heappop(rest)

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        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
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

import heapq as hp
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
uni = UnionFind(N-1)
for _ in range(M):
    a, b = map(int, input().split())
    uni.Unite(a, b)

root = {}
for i in range(N):
    r = uni.Find_Root(i)
    if not r in root.keys():
        root[r] = [A[i]]
    else:
        hp.heappush(root[r], A[i])
B = sorted(root.values(), reverse=True, key=lambda x:len(x))
q = []
ok = True
ans = 0
for i, L in enumerate(B):
    if i == 0:
        for a in L:
            hp.heappush(q, a)
    else:
        if not q:
            ok = False
            break
        a1 = hp.heappop(q)
        a2 = hp.heappop(L)
        ans += a1 + a2
        for a in L:
            hp.heappush(q, a)
if not ok:
    print("Impossible")
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
n,m,*a=map(int,open(0).read().split())
t=[-1]*n
def r(x):
  while t[x]>=0:x=t[x]
  return x
def u(x,y):
  x,y=r(x),r(y)
  if x!=y:
    if t[x]>t[y]:x,y=y,x
    t[x]+=t[y]
    t[y]=x
d=defaultdict(list)
for x,y in zip(*[iter(a[n:])]*2):u(x,y)
for i,v in enumerate(a[:n]):d[r(i)]+=v,
if len(d)<2:
  print(0)
  exit()
*d,=map(sorted,d.values())
c=sum(heappop(t)for t in d)
l=[]
for t in d:l+=t
i=len(d)-2
print(i>len(l)and'Impossible'or c+sum(sorted(l)[:i]))

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
def main():
  n,m,*a=map(int,open(0).read().split())
  table=[-1]*n
  def root(x):
    while table[x]>=0:x=table[x]
    return x
  def unite(x,y):
    s1=root(x)
    s2=root(y)
    if s1!=s2:
      if table[s1]>table[s2]:s1,s2=s2,s1
      table[s1]+=table[s2]
      table[s2]=s1
  d=defaultdict(list)
  for x,y in zip(*[iter(a[n:])]*2):unite(x,y)
  for i,v in enumerate(a[:n]):d[root(i)]+=v,
  if len(d)<2:
    print(0)
    return
  *d,=map(sorted,d.values())
  c=sum(heappop(t)for t in d)
  l=[]
  for t in d:l+=t
  i=len(d)-2
  if len(l)<i:
    print('Impossible')
  else:
    print(c+sum(sorted(l)[:i]))
main()

Submission status: Accepted

Solution code:
def main():
    import sys,heapq
    input = sys.stdin.readline

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


    #Union Find
    par = [-1]*n
    #xの根を求める
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    #xとyの属する集合の併合
    def unite(x,y):
        x = find(x)
        y = find(y)

        if x == y:
            return False
        else:
            #sizeの大きいほうがx
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True

    #xとyが同じ集合に属するかの判定
    def same(x,y):
        return find(x) == find(y)

    #xが属する集合の個数
    def size(x):
        return -par[find(x)]


    for _ in [0]*m:
        x,y = map(int,input().split())
        unite(x,y)
    
    if m < (n-1)//2:
        print('Impossible')
        return
    
    h = [[] for _ in [0]*n]
    for i,e in enumerate(a):
        heapq.heappush(h[find(i)],e)
    
    root = []
    for i,e in enumerate(par):
        if e < 0:
            root.append(i)
    
    if len(root) == 1:
        print(0)
        return

    must = 0
    opt = []
    for i in root:
        must += heapq.heappop(h[i])
        for e in h[i]:
            opt.append(e)
    opt.sort()

    print(must+sum(opt[:len(root)-2]))



if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

class UnionFind :
    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component

N, M = map(int, input().split())
A = [(a, i) for i, a in enumerate(map(int, input().split()))]
INF = float('inf')

tree = UnionFind(N)

for _ in range(M):
    a, b = map(int, input().split())
    tree.union(a, b)

A.sort()
ans = 0
L = (tree.getComponent() - 1) * 2

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

V = set()
for j, (a, i) in enumerate(A):
    r = tree.root(i)
    if not r in V:
        ans += a
        V.add(r)
        L -= 1
        A[j] = (INF, i)

A.sort()
for a, _ in A[:L]:
    ans += a

if ans == INF:
    print('Impossible')
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


parent_data = []

def union(ind):
    global parent_data
    if parent_data[ind] != ind:
        parent_data[ind] = union(parent_data[ind])
    return parent_data[ind]


def main():
    node_num, edge_num = map(int, input().split())
    cost_data = list(map(int, input().split()))
    data = [list(map(int, input().split())) for i in range(edge_num)]

    global parent_data
    parent_data = [i for i in range(node_num)]

    for i in range(edge_num):
        a, b = data[i]
        parent_a = union(a)
        parent_b = union(b)
        parent_data[min(parent_a, parent_b)] = max(parent_a, parent_b)

    parent_count = defaultdict(int)
    cost_heap = defaultdict(list)
    for i in range(node_num):
        parent_i = union(i)
        parent_count[parent_i] += 1
        heapq.heappush(cost_heap[parent_i], (cost_data[i], parent_i))

    parent_count = list(sorted(parent_count.items(), key=lambda x:-x[1]))

    ans = 0
    ori_ind, ori_count = parent_count[0]

    for i in range(len(parent_count) - 1):
        now_ind, now_count = parent_count[i + 1]
        if len(cost_heap[ori_ind]) == 0:
            print('Impossible')
            sys.exit()
        ori_cost, o_ind = heapq.heappop(cost_heap[ori_ind])
        now_cost, n_ind = heapq.heappop(cost_heap[now_ind])
        ans += ori_cost + now_cost

        if len(cost_heap[n_ind]) > 0:
            a, b = heapq.heappop(cost_heap[n_ind])
            heapq.heappush(cost_heap[ori_ind], (a, b))
        if len(cost_heap[o_ind]) > 0 and o_ind != ori_ind:
            a, b = heapq.heappop(cost_heap[o_ind])
            heapq.heappush(cost_heap[ori_ind], (a, b))

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N,M = map(int,input().split())
A = np.array(input().split(),dtype=np.int64)
XY = [[int(x) for x in input().split()] for _ in range(M)]

if M>0:
    X,Y = zip(*XY)
else:
    X,Y = [],[]
n_comp,comp = connected_components(csr_matrix(([1]*M,(X,Y)),(N,N)))

i = np.lexsort((A,comp))
A = A[i]; comp = comp[i]

i = np.concatenate([[0],np.where(comp[1:] != comp[:-1])[0]+1])

cost = A[i].sum()
A = np.delete(A,i)
rest = 2 * (n_comp-1) - len(i)
if n_comp == 1:
    print(0)
elif rest > len(A):
    print('Impossible')
else:
    A.sort()
    cost += A[:rest].sum()
    print(cost)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.root(x)]


N, M = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
XY = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

uf = UnionFind(size=N)
for x, y in XY:
    uf.unite(x, y)

# N-M 個の木がある
if N - M == 1:
    print(0)
    exit()
if (N - M - 1) * 2 > N:
    print('Impossible')
    exit()

A = np.array(A, dtype=int)
idx = A.argsort()

ans = 0
cnt = 0
used_n = np.zeros(N, dtype=bool)
used_root = np.zeros(N, dtype=bool)
for i in idx:
    if not used_root[uf.root(i)]:
        used_root[uf.root(i)] = True
        used_n[i] = True
        ans += A[i]
        cnt += 1

for i in idx:
    if not used_n[i]:
        ans += A[i]
        cnt += 1
    if cnt >= (N - M - 1) * 2:
        break
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys


def dfs(adj, start, visited, cost):
    que = deque()
    que.append(start)
    cost_list = []
    while que:
        v = que.pop()
        visited[v] = 1
        cost_list.append(cost[v])
        for u in adj[v]:
            if visited[u] == 0:
                que.append(u)
    visited_ret = visited
    return sorted(cost_list), visited_ret


N, M = map(int, input().split())
cost = list(map(int, input().split()))
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

visited = [0] * N
cost_lists = []
for i in range(N):
    if visited[i] == 0:
        cost_list, visited = dfs(adj, i, visited, cost)
        cost_lists.append(cost_list)

if len(cost_lists) == 1:
    print(0)
    sys.exit()

ans = 0
pool = []
for i, cost_list in enumerate(cost_lists):
    for j, cost in enumerate(cost_list):
        if j == 0:
            ans += cost
        else:
            pool.append(cost)
pool.sort()
for i in range(len(cost_lists) - 2):
    if i < len(pool):
        ans += pool[i]
    else:
        print('Impossible')
        sys.exit()
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
n,m = map(int, input().split())
a = list(map(int, input().split()))

uf = [-1]*n
def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx == ry:
        return False
    if uf[rx] > uf[ry]:
        rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

for i in range(m):
    x,y = map(int, input().split())
    unite(x,y)
if m == n-1:
    print(0)
elif (n-m-1)*2 > n:
    print("Impossible")
else:
    d = defaultdict(list)
    for i in range(n):
        heappush(d[root(i)], a[i])
    cnt = (n-m-1)*2
    ans = 0
    heap = []
    for value in d.values():
        ans += heappop(value)
        cnt -= 1
        while value:
            heappush(heap, heappop(value))
    for _ in range(cnt):
        ans += heappop(heap)
    print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify


class UnionFindTree():
    def __init__(self, N):
        self.N = N
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(self.N):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    uft = UnionFindTree(N)
    for _ in range(M):
        x, y = map(int, input().split())
        uft.unite(x, y)
    groups = uft.groups()
    if len(groups) == 1:
        print(0)
        return
    ans = 0
    h = []
    for g in groups:
        costs = [A[x] for x in g]
        costs.sort()
        ans += costs[0]
        for cost in costs[1:]:
            heappush(h, cost)
    if len(groups) == 2 and N == 2:
        print(ans)
        return
    if len(h) < len(groups)-2:
        print("Impossible")
        return
    for _ in range(len(groups)-2):
        ans += heappop(h)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import groupby

# 出力
N, M = map(int, input().split())
a = list(map(int, input().split()))
x, y = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)


class UnionFindTree:
    def __init__(self, n):
        self.p = [i for i in range(n + 1)]
        self.r = [0 for _ in range(n + 1)]

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

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.r[px] < self.r[py]:
                self.p[px] = py
            else:
                self.p[py] = px
                if self.r[px] == self.r[py]:
                    self.r[px] += 1

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


# 各連結成分のうち、a_iが最小の頂点は必ず使う
# 不足している分はa_iが小さい頂点から順に補えばよい
uft = UnionFindTree(N - 1)
for X, Y in zip(x, y):
    uft.union(X, Y)

C = [
    sorted(c, key=lambda i: a[i])
    for _, c in groupby(
        sorted(range(N), key=uft.find),
        uft.find
    )
]

K = 2 * (len(C) - 1)
S = {c[0] for c in C}

ans = (
    'Impossible' if K > N else
    0 if K == 0 else
    sum(a[s] for s in S) +
    sum(sorted(a[i] for i in range(N) if i not in S)[:(K - len(C))])
)

# 出力
print(ans)

Submission status: Accepted

Solution code:
import collections, heapq
N, M = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(M)]
G = collections.defaultdict(list)
for x, y in XY:
    G[x] += [y]
    G[y] += [x]
B = sorted([v, i] for i, v in enumerate(A))
visited = [0] * N
ans = 0
H = []
t = 0
for b in B:
    v, i = b
    if not visited[i]:
        visited[i] = 1
        ans += v
        q = G[i]
        t += 1
        while q:
            i = q.pop()
            if not visited[i]:
                visited[i] = 1
                heapq.heappush(H, [A[i], i])
                q += G[i]
if len(H) < t - 2:
    print('Impossible')
    exit()
elif t == 1:
    print(0)
    exit()
for _ in range(t - 2):
    v, i = heapq.heappop(H)
    ans += v
print(ans)

Submission status: Accepted

Solution code:
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):
#    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,y)だと無限ループ。
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

#import sys
#input = sys.stdin.readline
import heapq
def main():
    N, M = map( int, input().split())
    A = list( map( int, input().split()))
    V = [ i for i in range(N)]
    q = []
    for _ in range(M):
        x, y = map( int, input().split())
        union(V, x, y)
    C = [0]*N
    T = [ [] for _ in range(N)]
    for i in range(N):
        C[find(V,i)] += 1
        heapq.heappush(T[find(V,i)], A[i])
    ans = 0
    if M == 0 and N == 1:
        print(0)
        return
    if M == 0:
        print("Impossible")
        return
    s = 0
    for i in range(N):
        if C[i] >= 2:
            if s == 0:
                q = T[i]
                heapq.heapify(q)
                s = 1
                continue
            if q:
                ans += heapq.heappop(q)
                ans += heapq.heappop(T[i])
                for a in T[i]:
                    heapq.heappush(q, a)
            else:
                print("Impossible")
                return
    for i in range(N):
        if C[i] == 1:
            if q:
                ans += heapq.heappop(q)
                ans += T[i][0]
            else:
                print("Impossible")
                return
    print(ans)
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

def input():
    return sys.stdin.readline()[:-1]

n, m = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]
k = 0

pqs = []
edge = [[] for _ in range(n)]
for i in range(m):
    x, y = [int(item) for item in input().split()]
    edge[x].append(y)
    edge[y].append(x)

def dfs(n):
    kind[n] = k
    heappush(pqs[k], a[n])
    for item in edge[n]:
        if kind[item] == -1:
            dfs(item)

kind = [-1] * n
for i, item in enumerate(kind):
    if item == -1:
        pqs.append([])
        dfs(i)
        k += 1

if k == 1:
    print(0)
    exit()
    
ans = 0
for i in range(k):
    val = heappop(pqs[i])
    ans += val
pqs = [flatten for inner in pqs for flatten in inner] 
pqs.sort()
for i in range(k-2):
    if i > len(pqs) - 1:
        print("Impossible")
        exit()
    ans += pqs[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def input():
	return sys.stdin.readline()[:-1]

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

root = [-1 for _ in range(n)]
is_minimum = [False for _ in range(n)]

def dfs(x, r):
	global mi, mi_ind
	if a[x] < mi:
		mi = a[x]
		mi_ind = x
	for v in adj[x]:
		if root[v] < 0:
			root[v] = r
			dfs(v, r)
	return mi_ind

for i in range(n):
	if root[i] < 0:
		mi, mi_ind = 10**10, -1
		root[i] = i
		is_minimum[dfs(i, i)] = True

con_num = len(set(root))
#print(con_num)
if (con_num-1) * 2 > n:
	print("Impossible")
	sys.exit()
elif con_num == 1:
	print(0)
	sys.exit()
ans = sum([a[i] for i in range(n) if is_minimum[i]])
ans += sum(sorted([a[i] for i in range(n) if not is_minimum[i]])[:con_num-2])
print(ans)

Submission status: Accepted

Solution code:
# python template for atcoder1
import heapq
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
# -*- coding: utf-8 -*-
# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N, L):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]
        self.costs = [[l] for l in L]

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

    def union(self, x, y) -> "min cost":
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
            for new_mem in self.costs[px]:
                heapq.heappush(self.costs[py], new_mem)
            self.costs[px] = []
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]
            for new_mem in self.costs[py]:
                heapq.heappush(self.costs[px], new_mem)
            self.costs[py] = []

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

    def get_parents(self) -> "list":
        return [i for i, p in enumerate(self.parent) if i == p]


N, M = map(int, input().split())
L = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(M)]

Un = UnionFind(N, L)
for s, g in edges:
    Un.union(s, g)


if M == N-1:
    print(0)
elif N < 2*(N-M-1):
    print("Impossible")
else:
    cost = 0
    cnt = 0
    for l in Un.get_parents():
        cost += heapq.heappop(Un.costs[l])
        cnt += len(Un.costs[l])

    remain_l = []
    for l in Un.get_parents():
        for v in Un.costs[l]:
            heapq.heappush(remain_l, v)
    for _ in range(2*(N-M-1)-len(Un.get_parents())):
        cost += heapq.heappop(remain_l)
    print(cost)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, input().split())
if N - 1 == M:
    print(0)
    exit()
if N < 2 * (N - M - 1):
    print('Impossible')
    exit()


parent = [i for i in range(N)]
rank = [0] * N


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


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


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


A = list(map(int, input().split()))
G = [[] for i in range(N)]
X, Y = [], []
for i in range(M):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)
    unite(x, y)

K = 0
D = defaultdict(list)
for i in range(N):
    k = find(i)
    if not D[k]:
        K += 1
    D[k].append((A[i], i))

ans = 0
used = [0] * N
for v in D.values():
    s = min(v)
    ans += s[0]
    used[s[1]] = 1

T = []
for i in range(N):
    if not used[i]:
        T.append(A[i])

T = sorted(T)
ans += sum(T[:2 * (N - M - 1) - K])
print(ans)