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: Time Limit Exceeded

Solution code:
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    xy=[list(map(int,input().split())) for _ in [0]*m]

    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree=[[i,1] for i in range(self.size)]#root,depth
        
        #rootを探す
        def root(self,index):
            temp_list=[]
            temp=self.tree[index][0]
            while index!=temp:
                temp_list.append(index)
                index=temp
                temp=self.tree[index][0]
            for i in temp_list:
                self.tree[i][0]=index
            return index
    
        #結合
        def unite(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1!=r2:
                d1,d2=self.tree[r1][1],self.tree[r2][1]
                if d1<=d2:
                    self.tree[r1][0]=r2
                    self.tree[r2][1]=max(d1+1,d2)
                else:
                    self.tree[r2][0]=r1
                    self.tree[r1][1]=max(d2+1,d1)
    
        #同じか判定
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
    
        #連結成分の個数
        def component(self):
            return len({self.root(i) for i in range(self.size)})
    
    u=unionfind(n)
    for x,y in xy:
        u.unite(x,y)
    for i in range(n):
        u.tree[i][0]=u.root(i)
    ut=u.tree
    d=dict()
    for i in range(n):
        if ut[i][0] in d.keys():
            d[ut[i][0]].append(a[i])
        else:
            d[ut[i][0]]=[a[i]]
    list1=[]
    list2=[]
    for s in d.values():
        s2=sorted(s)
        list1.append(s2[0])
        list2+=s2[1:]
    if len(list1)==1:
        print(0)
    elif len(list1)>len(list2)+2:
        print("Impossible")
    else:
        list2.sort()
        print(sum(list1)+sum(list2[:len(list1)-2]))
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m=map(int,input().split())
    a=list(map(int,input().split()))
    xy=[list(map(int,input().split())) for _ in [0]*m]
    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree=[[i,1] for i in range(self.size)]#root,depth
        
        #rootを探す
        def root(self,index):
            if self.tree[index][0]==index:
                return index
            else:
                self.tree[index][0]=self.root(self.tree[index][0])
                return self.tree[index][0]
    
        #結合
        def unite(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1!=r2:
                d1,d2=self.tree[r1][1],self.tree[r2][1]
                if d1<=d2:
                    self.tree[r1][0]=r2
                    self.tree[r2][1]=max(d1+1,d2)
                else:
                    self.tree[r2][0]=r1
                    self.tree[r1][1]=max(d2+1,d1)
    
        #同じか判定
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
    
        #連結成分の個数
        def component(self):
            return len({self.root(i) for i in range(self.size)})
    
    u=unionfind(n)
    for x,y in xy:
        u.unite(x,y)
    for i in range(n):
        u.tree[i][0]=u.root(i)
    ut=u.tree
    d=dict()
    for i in range(n):
        if ut[i][0] in d.keys():
            d[ut[i][0]].append(a[i])
        else:
            d[ut[i][0]]=[a[i]]
    list1=[]
    list2=[]
    for s in d.values():
        s2=sorted(s)
        list1.append(s2[0])
        list2+=s2[1:]
    if len(list1)==1:
        print(0)
    elif len(list1)>len(list2)+2:
        print("Impossible")
    else:
        list2.sort()
        print(sum(list1)+sum(list2[:len(list1)-2]))
main()

Submission status: Time Limit Exceeded

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]: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: Time Limit Exceeded

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_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 = heapq.heappop(cost_heap[ori_ind])
        now_cost = heapq.heappop(cost_heap[now_ind])
        ans += ori_cost + now_cost
        cost_heap[ori_ind] = list(heapq.merge(cost_heap[ori_ind], cost_heap[now_ind]))

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 = sum(pqs, [])
pqs.sort()
for i in range(k-2):
    if i > len(pqs) - 1:
        print("Impossible")
        exit()
    ans += pqs[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
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
    heapq.heappush(pqs[k], a[n])
    for item in edge[n]:
        if kind[item] != -1:
            continue
        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 = heapq.heappop(pqs[i])
    ans += val
pqs = sum(pqs, [])
pqs.sort()
for i in range(k-2):
    if i > len(pqs) - 1:
        print("Impossible")
        exit()
    ans += pqs[i]
print(ans)

Submission status: Time Limit Exceeded

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

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
    heapq.heappush(pqs[k], a[n])
    for item in edge[n]:
        if kind[item] != -1:
            continue
        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 = heapq.heappop(pqs[i])
    ans += val
pqs = sum(pqs, [])
pqs.sort()
for i in range(k-2):
    if i > len(pqs) - 1:
        print("Impossible")
        exit()
    ans += pqs[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
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
    heapq.heappush(pqs[k], a[n])
    for item in edge[n]:
        if kind[item] != -1:
            continue
        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 = heapq.heappop(pqs[i])
    ans += val
pqs = sum(pqs, [])
pqs.sort()
for i in range(k-2):
    if i > len(pqs) - 1:
        print("Impossible")
        exit()
    ans += pqs[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import bisect
 
def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

def main():
  N, M = reads()
  A = reads()

  d = Counter(A)
  uf = union_find(N)
  edges = [[] for _ in range(N)]
  for _ in range(M):
    x, y = reads()
    uf.unite(x, y)

  INF = 1 << 30
  mins = defaultdict(lambda: INF)
  for i in range(N):
    k = uf.root(i)
    mins[k] = min(mins[k], A[i])
  g = len(mins)

  if g == 1:
    print(0); exit()
  if (g - 1) * 2 > N:
    print("Impossible"); exit()

  ans = 0
  for k, v in mins.items():
    ans += v
    d[v] -= 1
  ans += sum(sorted(d.elements())[:g-2])
  print(ans)
  

class union_find:
  def __init__(self, n):
    self.par = [-1] * n
  def __repr__(self):
    return "union_find({0})".format(self.par)
  def unite(self, x, y):
    if self.root(x) != self.root(y):
      self.par[self.root(x)] = y
  def root(self, x):
    if self.par[x] == -1:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  def same(self, x, y):
    return self.root(x) == self.root(y)

main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

#
N, M = list(map(int, input().split()))
S = list(map(int, input().split()))
groups = [[x] for x in range(N)]
for i in range(M):
    a, b = list(map(int, input().split()))
    id = []
    tmp = -1
    for i in range(len(groups)):
        if a in groups[i] and not b in groups[i]:
            id.append(i)
            tmp = b
        if b in groups[i] and not a in groups[i]:
            id.append(i)
            tmp = a
    if len(id)==2:
        groups[id[0]] += groups[id[1]]
        del groups[id[1]]
    elif len(id)==1:
        groups[id[0]].append(tmp)
    else:
        groups.append([a, b])
#print(groups)
G = [[] for _ in range(len(groups))]
for i in range(len(groups)):
    for j in groups[i]:
        heappush(G[i], S[j])
#print(G)

#
if len(G)==1:
    print(0)
    exit()
#if M<(len(G)-1)*2:
#    print('Impossible')
#    exit()
need = (len(G)-1)*2
if N<need:
    print('Impossible')
    exit()

#
ans = 0
rest = []
for g in G:
    ans += heappop(g)
    for i in g:
        heappush(rest, i)
need -= len(G)
if len(rest)<need:
    print('Impossible')
    exit()

ans += sum(rest[:need])
#print(ans, G)
# for i in range(need):
#     tmp = [g[0] for g in G]
#     m = min(tmp)
#     ans += m
#     id = tmp.index(m)
#     pushpop(G[id])#del G[id][0]
print(ans)

Submission status: Time Limit Exceeded

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


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


def main():
    N, M = map(int, readline().split())
    a = list(map(int, readline().split()))
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(int, readline().split())
        uf.union(x, y)
    mins = defaultdict(list)
    for i in range(N):
        heapq.heappush(mins[uf.find(i)], a[i])
    if len(mins) == 1:
        return 0
    ans = 0
    for v in mins.values():
        ans += heapq.heappop(v)
    other_a = sorted(sum(mins.values(), []))
    return 'Impossible' if len(other_a) < len(mins) - 2 else ans + sum(other_a[:len(mins) - 2])

print(main())

Submission status: Time Limit Exceeded

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


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False


def main():
    N, M = map(int, input().split())
    a = list(map(int, readline().split()))
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(int, input().split())
        uf.union(x, y)
    mins = defaultdict(list)
    for i in range(N):
        heapq.heappush(mins[uf.find(i)], a[i])
    if len(mins) == 1: return 0
    ans = 0
    for v in mins.values():
        ans += heapq.heappop(v)
    other_a = sorted(sum(mins.values(), []))
    return 'Impossible' if len(other_a) < len(mins) - 2 else ans + sum(other_a[:len(mins) - 2])

print(main())

Submission status: Time Limit Exceeded

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

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

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

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

    if st == N:
        break

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

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

conn_list.sort()

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

Submission status: Time Limit Exceeded

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

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

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

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

    if st == N:
        break

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

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

conn_list_ = sorted(conn_list)

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

Submission status: Accepted

Solution code:
#unionfind
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 __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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.union(x,y)
v=[[] for _ in range(n)]
for i in range(n):
    v[uf.find(i)].append((a[i],i))
flag=set()
ans,cnt=0,0
for t in v:
    if t:
        t.sort()
        c,idx=t[0]
        flag.add(idx)
        cnt+=1
        ans+=c
for i in range(n):
    a[i]=(a[i],i)
a.sort()
for i in range(n):
    if cnt==2*(n-m-1):
        break
    c,idx=a[i]
    if idx not in flag:
        ans+=c
        cnt+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
ki=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  ki[x].append(y)
  ki[y].append(x)
ans=0
cost=[]
mi=set(range(n))
cnt=0
from heapq import heappop,heappush,heapify
while mi:
  todo=[mi.pop()]
  g=[a[todo[0]]]
  while todo:
    v=todo.pop()
    for nv in ki[v]:
      if nv in mi:
        todo.append(nv)
        heappush(g,a[nv])
        mi.discard(nv)
  ans+=heappop(g)
  cost+=g
  cnt+=1
if cnt==1:
  print(0)
elif 2*(cnt-1)<=n:
  cost.sort()
  k=(cnt-1)*2-cnt
  ans+=sum(cost[:k])
  print(ans)
else:
  print('Impossible')

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import nsmallest

class UnionFind():
    "Either 0-indexed or 1-indexed"

    __slots__ = ["parent"]

    def __init__(self, size):
        self.parent = [-1] * (size + 1)
    
    def find(self, a):
        path = []
        while self.parent[a] >= 0:
            path.append(a)
            a = self.parent[a]
        for child in path:
            self.parent[child] = a
        return a

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)

        if a == b:
            return
        else:
            if self.parent[a] == self.parent[b]:
                self.parent[a] = b
                self.parent[b] -= 1
            elif self.parent[a] < self.parent[b]: #aのほうが大きい
                self.parent[b] = a
            else:
                self.parent[a] = b #bのほうが大きい
        
    def same(self, a, b):
        return self.find(a) == self.find(b)


N, M = map(int, input().split())
As = list(map(int, input().split()))
uf = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    uf.union(x, y)

anc_to_group = defaultdict(list)
for v in range(N):
    anc_to_group[uf.find(v)].append(v)

group_minima = []
remains = []
for group in anc_to_group.values():
    costs = [As[v] for v in group]
    minimum = min(costs)
    costs.remove(minimum)
    group_minima.append(minimum)
    remains += costs

if len(anc_to_group) == 1:
    print(0)
elif len(anc_to_group) - 2 > len(remains):
    print("Impossible")
else:
    ans = sum(group_minima)
    ans += sum(nsmallest((len(anc_to_group) - 2), remains))
    print(ans)

Submission status: Accepted

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

if (N-1-M)*2 > N:
    print('Impossible')
    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: [])
for i in range(N):
    r = uf.root(i)
    dic[r].append(A[i])
if len(dic)==1:
    print(0)
    exit()

ans = 0
arr = []
c = 0
for k in dic.keys():
    dic[k].sort(reverse=True)
    ans += dic[k].pop()
    c += 1
    for a in dic[k]:
        arr.append(a)
rem = (N-1-M)*2 - c
if rem > len(arr):
    print('Impossible')
else:
    arr.sort()
    ans += sum(arr[:rem])
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
A=list(map(int, input().split()))
if N-1==M:
  print(0)
  exit()
#連結成分の合計a,連結する辺の数b
a,b=N-M,N-M-1
if N<2*(N-M-1):
  print('Impossible')
  exit()

par=[i for i in range(N)]
rank=[0]*(N)
size=[1]*N

def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def same(x,y):
  return find(x)==find(y)
def union(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return 
  if rank[x]>rank[y]:
    par[y]=x
    size[x]+=size[y]
  else:
    par[x]=y
    size[y]+=size[x]
    if rank[x]==rank[y]:
      rank[y]+=1
      
for i in range(M):
  a,b=map(int,input().split())
  union(a,b)
D=[[10**9+1,-1] for i in range(N)]
C=[]
for i in range(N):
  a=find(i)
  if D[a][0]>A[i]:
    C.append([D[a][0],D[a][1]])
    D[a][0]=A[i]
    D[a][1]=i
  else:
    C.append([A[i],i])
ans=0
cnt=0
for a,b in D:
  if b!=-1:
    ans+=a
    cnt+=1
C=sorted(C)
for a,b in C:
  if cnt==2*(N-M-1):
    break
  ans+=a
  cnt+=1
print(ans)

Submission status: Accepted

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())

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

g=uf.group_count()

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

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

ans=0
all_costs=[]

from collections import defaultdict
costs=defaultdict(list)
for i in range(n):
    costs[uf.find(i)].append(a[i])

for k,v in costs.items():
    v.sort()
    ans+=v[0]
    all_costs.extend(v[1:])

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

print(ans)

Submission status: Accepted

Solution code:
import heapq

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

n,m=map(int,input().split())
costs=list(map(int,input().split()))
if m==n-1:
  print(0)
  exit()
edges=[list(map(int,input().split())) for _ in range(m)]
uf=UnionFind(n)
for a,b in edges:
  uf.Unite(a,b)
qs=[[] for _ in range(n)]
roots=set()
for i in range(n):
  root=uf.FindRoot(i)
  roots.add(root)
  heapq.heappush(qs[root],costs[i])
remains=[]
ans=0
cnt=0
for root in roots:
  cost=heapq.heappop(qs[root])
  ans+=cost
  cnt+=1
  while len(qs[root])!=0:
    cost=heapq.heappop(qs[root])
    heapq.heappush(remains,cost)
while len(remains)!=0 and cnt<2*(n-m-1):
  cost=heapq.heappop(remains)
  ans+=cost
  cnt+=1
if cnt==2*(n-m-1):
  print(ans)
else:
  print('Impossible')

Submission status: Accepted

Solution code:
import heapq

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

n,m=map(int,input().split())
cost=list(map(int,input().split()))
if n==1:
  print(0)
  exit()
if n==2:
  if m==0:
    print(cost[0]+cost[1])
    exit()
  if m==1:
    print(0)
    exit()
edges=[list(map(int,input().split())) for _ in range(m)]
uf=UnionFind(n)
for a,b in edges:
  uf.Unite(a,b)
isolates=set()
isolates_cnt=0
groups=set()
groups_cnt=2
roots=[]
qs=[[] for _ in range(n)]
for i in range(n):
  root=uf.FindRoot(i)
  cnt=uf.Count(i)
  if cnt==1:
    isolates_cnt+=1
    isolates.add(root)
    heapq.heappush(qs[root],(cost[i],i))
  else:
    if root not in groups:
      groups_cnt+=cnt-2
      roots.append((root,cnt))
    groups.add(root)
    heapq.heappush(qs[root],(cost[i],i))
if groups_cnt<isolates_cnt:
  print('Impossible')
else:
  ans=0
  roots=sorted(roots,reverse=True,key=lambda x:x[1])
  root=roots[0][0]
  for tmp_root,_ in roots[1:]:
    cv,v=heapq.heappop(qs[root])
    cu,u=heapq.heappop(qs[tmp_root])
    ans+=(cv+cu)
    while len(qs[tmp_root])!=0:
      tc,tv=heapq.heappop(qs[tmp_root])
      heapq.heappush(qs[root],(tc,tv))
  for tmp_root in isolates:
    cv,v=heapq.heappop(qs[root])
    cu,u=heapq.heappop(qs[tmp_root])
    ans+=(cv+cu)
  print(ans)