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:
from collections import defaultdict

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が属するグループに属する要素をリストで返す O(n)に注意
        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):  # {根: [グループに含まれる要素のリスト], ...}の辞書を返す O(n)に注意
        ret = defaultdict(list)
        for i in range(self.n):
            ret[self.find(i)].append(i)
        return ret

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

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

Solution code:
s=sorted
(n,m,*b),a,*q=[map(int,t.split())for t in open(0)]
t=[-1]*n
r=lambda x:r(t[x])if-1<t[x]else x
def u(x):
 x,y=map(r,x)
 if x-y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
*map(u,q),
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:
 if p:x,*y=s(p);c+=x;b+=y;j-=1
print((c+sum(s(b)[:j]),'Impossible')[k>n]*(k>0))

Submission status: Accepted

Solution code:
s=sorted
(n,m,*b),a,*q=[map(int,t.split())for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=map(r,x)
 if x-y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
*map(u,q),
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:
 if p:x,*y=s(p);c+=x;b+=y;j-=1
print((c+sum(s(b)[:j]),'Impossible')[k>n]*(k>0))

Submission status: Accepted

Solution code:
s=sorted
(n,m,*b),a,*q=[map(int,t.split())for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=map(r,x)
 if x-y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
[*map(u,q)]
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:
 if p:x,*y=s(p);c+=x;b+=y;j-=1
print((c+sum(s(b)[:j]),'Impossible')[k>n]*(k>0))

Submission status: Accepted

Solution code:
(n,m,*b),a,*q=[map(int,t.split())for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=map(r,x)
 if x-y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
[*map(u,q)]
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:
 if p:x,*y=sorted(p);c+=x;b+=y;j-=1
print((c+sum(sorted(b)[:j]),'Impossible')[k>n]*(k>0))

Submission status: Accepted

Solution code:
(n,m,*b),a,*q=[map(int,t.split())for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=map(r,x)
 if x-y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
[*map(u,q)]
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:x,*y=sorted(p)+[0];c+=x;b+=y[:-1];j-=p>[]
print((c+sum(sorted(b)[:j]),'Impossible')[k>n]*(k>0))

Submission status: Accepted

Solution code:
(n,m,*b),a,*q=[map(int,t.split())for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=map(r,x)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
[*map(u,q)]
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:x,*y=sorted(p)+[0];c+=x;b+=y[:-1];j-=p>[]
print((c+sum(sorted(b)[:j]),'Impossible')[k>n]*(k>0))

Submission status: Accepted

Solution code:
(n,m,*b),a,*q=[map(int,t.split())for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=map(r,x)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
[*map(u,q)]
i=c=0
k=j=n+~m<<1
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
for p in d:x,*y=sorted(p)+[0];c+=x;b+=y[:-1];j-=p>[]
print(k<1and'0'or(k>n)*'Impossible'or c+sum(sorted(b)[:j]))

Submission status: Accepted

Solution code:
(n,m),a,*q=[map(int,t.split())for t in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(x):
 x,y=map(r,x)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
[*map(u,q)]
i=c=0
k,*b=n+~m<<1,
*d,=eval('[],'*n)
for v in a:d[r(i)]+=v,;i+=1
print(k<1and'0'or(k>n)*'Impossible'or exec('for p in d:x,*y=sorted(p)+[0];c+=x;b+=y[:-1];k-=p>[]')or c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(L):
 x,y=map(r,L)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
d=defaultdict(list)
for l in q:u(l)
i=c=0;b=[];k=(n+~m)*2
for v in a:d[r(i)]+=v,;i+=1
print(k<1and'0'or(k>n)*'Impossible'or exec("for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1")or c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
t=[-1]*n
def r(x):
 while-1<t[x]:x=t[x]
 return x
def u(L):
 x,y=map(r,L)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
d=defaultdict(list)
for l in q:u(l)
i=c=0;b=[];k=(n+~m)*2
for v in a:d[r(i)]+=v,;i+=1
print(k<1and'0'or k>n and'Impossible'or exec("for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1")or c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
t=[-1]*n
def r(x):
 while t[x]>=0:x=t[x]
 return x
def u(L):
 x,y=map(r,L)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
d=defaultdict(list)
for l in q:u(l)
i=c=0;b=[];k=(n+~m)*2
for v in a:d[r(i)]+=v,;i+=1
print(k<1and'0'or k>n and'Impossible'or exec("for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1")or c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
t=[-1]*n
def r(x):
 while t[x]>=0:x=t[x]
 return x
def u(L):
 x,y=map(r,L)
 if x!=y:
  if t[x]>t[y]:x,y=y,x
  t[x]+=t[y];t[y]=x
d=defaultdict(list)
for l in q:u(l)
i=c=0;b=[];k=(n+~m)*2
for v in a:d[r(i)]+=v,;i+=1
print(k<1and'0'or k>n and'Impossible'or exec("for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1")or c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
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 q:u(x,y)
i=c=0;b=[];k=(n+~m)*2
for v in a:d[r(i)]+=v,;i+=1
print(k<1and'0'or k>n and'Impossible'or exec("for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1")or c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
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 q:u(x,y)
i=c=0;b=[];k=(n+~m)*2;f=print
for v in a:d[r(i)]+=v,;i+=1
print(0if k<1else'Impossible'if k>n else exec("for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1")or c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
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 q:u(x,y)
i=c=0;b=[];k=(n+~m)*2;f=print
for v in a:d[r(i)]+=v,;i+=1
if k<1:f(0)
elif k>n:f('Impossible')
else:
 for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1
 f(c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
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 q:u(x,y)
i=c=0;b=[];k=(n+~m)*2
for v in a:d[r(i)]+=v,;i+=1
if k<1:print(0)
elif k>n:print('Impossible')
else:
 for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1
 print(c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
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 q:u(x,y)
i=c=0;b=[]
for v in a:d[r(i)]+=v,;i+=1
if(k:=(n+~m)*2)<1:exit(print(0))
for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1
print(k>len(b)and'Impossible'or c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
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 q:u(x,y)
i=c=0;b=[]
for v in a:d[r(i)]+=v,;i+=1
if(k:=n+~m)<1:exit(print(0))
k*=2
for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1
print(k>len(b)and'Impossible'or c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
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 q:u(x,y)
i=c=0;b=[]
for v in a:d[r(i)]+=v,;i+=1
k=n+~m
if k<1:exit(print(0))
k*=2
for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1
print(k>len(b)and'Impossible'or c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
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 q:u(x,y)
i=c=0;b=[];k=(n+~m)*2
for v in a:d[r(i)]+=v,;i+=1
if k<1:exit(print(0))
for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1
print(k>len(b)and'Impossible'or c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
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 q:u(x,y)
i=0
for v in a:d[r(i)]+=v,;i+=1
if len(d)<2:exit(print(0))
c,b,k=0,[],(n-m-1)*2
for r,p in d.items():p.sort();c+=p.pop(0);b+=p;k-=1
print(k>len(b)and'Impossible'or c+sum(sorted(b)[:k]))

Submission status: Accepted

Solution code:
from collections import*
from heapq import*
(n,m),a,*q=[[*map(int,o.split())]for o in open(0)]
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 q:u(x,y)
i=0
for v in a:d[r(i)]+=v,;i+=1
if len(d)<2:exit(print(0))
*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 heapq import heapify, heappop, heappush

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

N,M = map(int,input().split())
A = list(map(int,input().split()))
if N == M +1:
  print(0)
  exit()
Cost = []
for i in range(N):
  heappush(Cost,[A[i],i]) #コスト、IDという順で保存。
uf = UnionFind(N)
for i in range(M):
  a,b = map(int,input().split())
  #a-=1;b-=1 #既に0index
  uf.union(a,b)
ans = 0
L = [[] for _ in range(N-M)]
dic = {}
num = 0
for i in range(N):
  par = uf.find(i)
  if par not in dic:
    dic[par] = num
    heappush(L[dic[par]],[A[i],i])
    num +=1
  else:
    heappush(L[dic[par]],[A[i],i])
#print(L)
Selected = set([])
for x in L:
  ans += x[0][0] #最小のコスト
  Selected.add(x[0][1]) #頂点
#print(Selected)
ima = N-M
while ima < 2*(N-M-1) and Cost:
  cost, ID = heappop(Cost)
  if ID in Selected:
    continue
  else:
    ans += cost
    ima += 1
if ima < 2*(N-M-1):
  print("Impossible")
else:
  print(ans)

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 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())

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

    def get_all_members(self):
        pare_d = {}
        for i in range(self.n):
            parent = self.find(i)
            pare_d.setdefault(parent,[])
            pare_d[parent].append(i)
        return list(pare_d.values())

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



def main():
    n,m = map(int, input().split())
    al = list(map(int, input().split()))    
    uf = UnionFind(n)
    for _ in range(m):
        x,y = map(int, input().split())
        uf.union(x,y)

    first_mins = []
    other_vals = []
    
    all_members = uf.get_all_members()
    # all_members = list(uf.all_group_members())
    if len(all_members) == 1:
        print(0)
        exit()

    for members in all_members:
        vs = []
        for m in members:
            vs.append(al[m])
        vs.sort()
        first_mins.append(vs[0])
        for i,v in enumerate(vs[1:]):
            # if i > 0:
            other_vals.append(v)

    # print(first_mins)
    ans = 0
    ans += sum(first_mins)
    rem = len(all_members)-2
    if len(other_vals) < rem:
        print('Impossible')
        exit()
    other_vals.sort()
    ans += sum(other_vals[:rem])
    print(ans)



if __name__ == "__main__":
    main()

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 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())

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

    def get_all_members(self):
        pare_d = {}
        for i in range(self.n):
            parent = self.find(i)
            pare_d.setdefault(parent,[])
            pare_d[parent].append(i)
        return list(pare_d.values())

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



def main():
    n,m = map(int, input().split())
    al = list(map(int, input().split()))    
    uf = UnionFind(n)
    for _ in range(m):
        x,y = map(int, input().split())
        uf.union(x,y)

    first_mins = []
    other_vals = []
    
    all_members = uf.get_all_members()
    if len(all_members) == 1:
        print(0)
        exit()

    for members in all_members:
        vs = []
        for m in members:
            vs.append(al[m])
        vs.sort()
        first_mins.append(vs[0])
        for i,v in enumerate(vs[1:]):
            # if i > 0:
            other_vals.append(v)

    # print(first_mins)
    ans = 0
    ans += sum(first_mins)
    rem = len(all_members)-2
    if len(other_vals) < rem:
        print('Impossible')
        exit()
    other_vals.sort()
    ans += sum(other_vals[:rem])
    print(ans)



if __name__ == "__main__":
    main()

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 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())

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

    def get_all_members(self):
        pare_d = {}
        for i in range(self.n):
            parent = self.find(i)
            pare_d.setdefault(parent,[])
            pare_d[parent].append(i)
        return list(pare_d.values())

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



def main():
    n,m = map(int, input().split())
    al = list(map(int, input().split()))    
    uf = UnionFind(n)
    for _ in range(m):
        x,y = map(int, input().split())
        uf.union(x,y)

    first_mins = []
    other_vals = []
    
    all_members = uf.get_all_members()
    if len(all_members) == 1:
        print(0)
        exit()

    for members in all_members:
        vs = []
        for m in members:
            vs.append(al[m])
        vs.sort()
        first_mins.append(vs[0])
        for i,v in enumerate(vs):
            if i > 0:
                other_vals.append(v)

    # print(first_mins)
    ans = 0
    ans += sum(first_mins)
    rem = len(all_members)-2
    if len(other_vals) < rem:
        print('Impossible')
        exit()
    other_vals.sort()
    ans += sum(other_vals[:rem])
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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())

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

(n, m), a, *q = [[*map(int,o.split())] for o in open(0)]
UF = UnionFind(n)
k = (n - m - 1) * 2
if k > n:
    exit(print("Impossible"))
if not k:
    exit(print(0))

for c, f in q:
    UF.union(c, f)

from collections import*
d = defaultdict(list)
for e, i in enumerate(a):
    d[UF.find(e)] += i,

ans, b = 0, []
for r, p in d.items():
    p.sort()
    ans += p.pop(0)
    b += p
    k -= 1
b.sort()
print(ans + sum(b[:k]))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
from collections import defaultdict

class MeldableHeap():
    def __init__(self):
        self.size = 0
        self.heap = list()
        self.added = 0

    def top(self):
        if not self.heap:
            return None
        return self.heap[0] + self.added

    def pop(self):
        if not self.heap:
            return None
        res = heappop(self.heap)
        self.size -= 1
        return res + self.added

    def push(self, x):
        heappush(self.heap, x - self.added)
        self.size += 1

    def add(self, x):
        self.added += x

    def meld(self, other): #破壊的
        res = MeldableHeap()
        if self.size < other.size:
            self, other = other, self
        res.heap = self.heap
        res.size = self.size
        for _ in range(other.size):
            res.push(other.pop() - self.added)
        return res

N, M = map(int, input().split())
A = list(map(int, input().split()))
edge = [tuple(map(int, input().split())) for _ in range(M)]

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

for x, y in edge:
    graph[x].append(y)
    graph[y].append(x)

used = [0 for _ in range(N)]
heap = defaultdict(MeldableHeap)
roots = []

for root in range(N):
    if used[root]:
        continue
    roots.append(root)
    heap[root].push(A[root])
    used[root] = 1
    stack = [root]
    while stack:
        node = stack.pop()
        for adj in graph[node]:
            if used[adj]:
                continue
            used[adj] = 1
            heap[root].push(A[adj])
            stack.append(adj)

single = set()

for k, v in heap.items():
    if v.size == 1:
        single.add(k)

roots.sort(key=lambda x: x in single)

res = 0
tmp = heap[roots[0]]

for i in range(1, len(roots)):
    if tmp.size == 0:
        print('Impossible')
        break
    v = heap[roots[i]]
    a = tmp.pop()
    b = v.pop()
    tmp = tmp.meld(v)
    res += a + b
else:
    print(res)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
f=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  f[x].append(y)
  f[y].append(x)
if m==n-1:
  print(0)
  exit()
if (n-m-1)*2>n:
  print('Impossible')
  exit()
from heapq import heappop,heappush,heapify
mi=set(list(range(n)))
dg={}
dg1c=[]
while mi:
  gk=mi.pop()
  #if len(f[gk])==0:
  #  dg1c.append(a[gk])
  #  continue
  todo=[gk]
  dg[gk]=[]
  while todo:
    v=todo.pop()
    dg[gk].append(a[v])
    for nv in f[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)
# 頂点が2以上ある連結成分の個数
ren=n-m-len(dg1c)
topheap=[]
ans=0
ary=[]
cnt=0
#print(dg)
#print(f)
#print(dg1c)

for k in dg.keys():
  t=min(dg[k])
  ans+=t
  cnt+=1
  dg[k].remove(t)
  ary+=dg[k]
ary.sort()
ans+=sum(ary[:(n-m-1)*2-cnt])
print(ans)

Submission status: Accepted

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

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

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 異なる集合に属する場合のみ併合
        if x != y:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]

n,m = readints()

a = readints()

u = UnionFind(n)
for i in range(m):
    x,y = readints()
    u.unite(x,y)

for i in range(n):
    u.find(i)

b = {}
for i in range(n):
    if u.par[i]<0:
        b[i] = (a[i],i)

for i,p in enumerate(u.par):    
    if p>=0 and b[p][0]>a[i]:
        b[p] = (a[i],i)

for v in b.values():
    a[v[1]]=10**10

a.sort()
if len(b)==1:
    print(0)
elif n < len(b)*2-2:
    print('Impossible')
else:
    print(sum([x[0] for x in b.values()]) + sum(a[:len(b)-2]))

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n
        self.tree = [True] * n
        self.grpcnt = n

    def find(self, x):
        """ 根の検索(グループ番号の取得) """
        t = []
        while self.par[x] != x:
            t.append(x)
            x = self.par[x]
        for i in t:
            self.par[i] = x
        return self.par[x]

    def union(self, x, y):
        """ 併合 """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        self.grpcnt -= 1
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            return self.grpcnt
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N, M = MAP()
A = LIST()
uf = UnionFind(N)
for i in range(M):
    a, b = MAP()
    uf.union(a, b)

L = uf.get_size()
K = (L-1) * 2 
if K > N:
    print('Impossible')
    exit()
elif K == 0:
    print(0)
    exit()

adjli = [[] for i in range(N)]
for i in range(N):
    root = uf.find(i)
    adjli[root].append(A[i])

ans = 0
B = []
for i in range(N):
    if adjli[i]:
        adjli[i].sort(reverse=1)
        ans += adjli[i].pop()
        B += adjli[i]
        K -= 1

B.sort()
ans += sum(B[:K])
print(ans)