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
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root


def main():
    N,M=MI()
    A=LI()

    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    for _ in range(M):
        x,y = MI()
        unite(x,y)
    
    need = N-1-M #N-1本の辺が必要で、今M本の辺がある
    need *= 2 #辺の2倍の点を使う
    if need > N:
        print("Impossible")
        return 
    if need == 0:
        print(0)
        return

    root = defaultdict(list)
    for i,a in enumerate(A):
        root[get_root(i)].append(a)

    ans = 0
    whole = []
    for list_ in root.values():
        list_.sort()
        ans += list_[0]
        whole.extend(list_[1:])
        need-=1
    whole.sort()
    ans += sum(whole[:need])
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
res = 0
if M == 0:
  if N == 1:
    print(0)
  elif N == 2:
    print(sum(a))
  else: print("Impossible")
  exit(0)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uf = UnionFind(N - 1)
for _ in range(M):
  u, v = map(int, input().split())
  uf.Unite(u, v)
hs = [[] for _ in range(N + 1)]
for x in range(N):
  y = uf.Find_Root(x)
  heapq.heappush(hs[y], a[x])
#print(hs)
c = 0
t = []
for x in range(N):
  if len(hs[x]):
    c += 1
    res += heapq.heappop(hs[x])
    t += hs[x]
t.sort()
#print(c, t, hs, res)
if c == 1:
  print(0)
  exit(0)
if len(t) < c - 2:
  print("Impossible")
  exit(0)
for i in range(c - 2):
  if i >= c - 2:
    print("Impossible")
    exit(0)
  res += t[i]
print(res)

Submission status: Accepted

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * 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.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1
uf = UnionFind(N)

for x,y in XY:
    if uf.is_same(x,y): continue
    uf.unite(x,y)

re = N - uf.count
if re==1:
    print(0)
    exit()
v = (re-1)*2
if v > N:
    print('Impossible')
    exit()

for i in range(N):
    uf.root(i)
ans = 0
used = [0]*N
d = {}
for i in range(N):
    r = uf.root(i)
    if r in d:
        if d[r][0] > A[i]:
            d[r] = (A[i], i)
    else:
        d[r] = (A[i], i)

for a,b in d.values():
    ans += a
    used[b] = 1
rem = v-re
notused = []
for i in range(N):
    if used[i]: continue
    notused.append(A[i])
notused.sort()
ans += sum(notused[:rem])
print(ans)

Submission status: Accepted

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

class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        p = x
        
        while not self.par[p]<0:
            p = self.par[p]
        
        while x!=p:
            tmp = x
            x = self.par[x]
            self.par[tmp] = p
        
        return p
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)
        
        if rx==ry: return False
        
        if self.rank[rx]<self.rank[ry]:
            rx, ry = ry, rx
        
        self.par[rx] += self.par[ry]
        self.par[ry] = rx
    
        if self.rank[rx]==self.rank[ry]:
            self.rank[rx] += 1
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

N, M = map(int, input().split())
a = list(map(int, input().split()))
uf = Unionfind(N)

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

d = defaultdict(list)
rs = set()

for i in range(N):
    r = uf.root(i)
    rs.add(r)
    d[r].append(a[i])

if len(rs)==1:
    print(0)
    exit()

if 2*(len(rs)-1)>N:
    print('Impossible')
    exit()
    
ans = 0

for k in d.keys():
    d[k].sort()
    ans += d[k][0]

l = []

for v in d.values():
    l += v[1:]

l.sort()
ans += sum(l[:len(rs)-2])

print(ans)

Submission status: Accepted

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

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

for x,y in XY:
    data[x].append(y)
    data[y].append(x)
visitedlst=[]

ittenai=set([i for i in range(0,N)])
while ittenai:
    q=ittenai.pop()
    stack=[q]
    visited=set()
    visited.add(q)
    while stack:
        q=stack.pop()
        for p in data[q]:
            if p not in visited:
                visited.add(p)
                ittenai.remove(p)
                stack.append(p)
    visitedlst.append(visited)
lst=[]
value=0
count=0
for visited in visitedlst:
    visited=sorted([A[i] for i in list(visited)])
    for i in visited[1:]:
        lst.append(i)
    value+=visited[0]
    count+=1
if count==1:
    print(0)

elif len(lst)<(count//2-1)*2+count%2:
    print("Impossible")
else:
    lst.sort()
    value+=sum(lst[:(count//2-1)*2+count%2])
    print(value)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
cost = list(map(int,input().split()))
ab = [list(map(int, input().split(' '))) for i in range(m)]
graph = [[] for i in range(n)]
visited = [0 for i in range(n)]
vers = []
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
for i in range(n):
  if visited[i] == 0:
    vers.append([])
    stack = [i]
    while stack:
      x = stack.pop()
      visited[x] = 1
      vers[-1].append((cost[x],x))
      for y in graph[x]:
        if visited[y] == 0:
          stack.append(y)
n_grph = len(vers)
if (n_grph-1)*2 > n:
  print("Impossible")
  exit()
for ver in vers:
  ver.sort()
visited = [0 for i in range(n)]
i = [i for i in range(n)]
costi = list(zip(cost,i))
costi.sort()
ans = 0
t = n_grph-2
if t >= 0:
  for ver in vers:
    ans += ver[0][0]
    visited[ver[0][1]] = 1

k = 0
while t > 0:
  c = costi[k][1]
  if visited[c] == 0:
    ans += costi[k][0]
    t -= 1
  k += 1
print(ans)

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    #############################################################
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            self.n = n
            # 正==子: 根の頂点番号 / 負==根: 連結頂点数

        def find(self, x):
            # 要素xが属するグループの根を返す
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            # 要素xが属するグループと要素yが属するグループとを併合する
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素xが属するグループのサイズ（要素数）を返す
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            # 要素の根をリストで返す
            return self.parent[x] < 0

        def roots(self):
            # すべての根の要素をリストで返す
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            # 要素xが属するグループに属する要素をリストで返す
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        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 = LI()
    a = LI()
    ans = 0
    uf = UnionFind(N)
    for _ in range(M):
        x,y = LI()
        if not uf.same(x,y):
            uf.unite(x,y)
    D = defaultdict(int)
    rep = defaultdict(bool)
    r = uf.roots()
    keep = [-1]*N
    for i in range(N):
        parent = uf.find(i)
        if (not D[parent]) or D[parent] > a[i]:
            D[parent] = a[i]
            keep[parent] = i
    for i in range(N):
        if keep[i]==-1:
            continue
        rep[keep[i]] = True
        ans += D[i]
    loop = uf.group_count()-2
    if loop==-1:
        print(0)
        return
    A = []
    for i,j in enumerate(a):
        A.append([j,i])
    A.sort()
    cur = 0
    for i in range(N):
        if cur>=loop:
            break
        if not rep[A[i][1]]:
            cur +=1
            ans += A[i][0]
    if cur<loop:
        print("Impossible")
        return
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
if N == 1:
  print(0)
  exit(0)
if M == 0 and (N > 2):
  print("Impossible")
  exit(0)
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]
uf = UnionFind(N)
d = [[] for _ in range(N)]
for _ in range(M):
  u, v = map(int, input().split())
  uf.Unite(u, v)
for i in range(N):
  d[uf.Find_Root(i)].append(a[i])
res = 0
x = []
y = 0
for i in range(N):
  d[i].sort(reverse = True)
  if len(d[i]):
    res += d[i].pop()
    y += 1
  x += d[i]
if y == 1:
  print(0)
  exit(0)
x.sort()
for i in range((y - 1) * 2 - y):
  if i >= len(x):
    print("Impossible")
    exit(0)
  res += x[i]
print(res)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.ps = [-1]*n
    def find(self,x):
        if self.ps[x]<0:
            return x
        else:
            self.ps[x]=self.find(self.ps[x])
            return self.ps[x]
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return False
        if self.ps[x]>self.ps[y]:
            x,y = y,x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True
    def same(self,x,y):
        return self.find(x)==self.find(y)
    def size(self,x):
        x = self.find(x)
        return -self.ps[x]

def main():
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  uf = UnionFind(n)
  for _ in range(m):
    x,y = map(int, input().split())
    uf.unite(x,y)
  d = dict()
  res = list()
  for i in range(n):
    v = uf.find(i)
    if v not in d:
      d[v] = a[i]
    elif d[v] > a[i]:
      res.append(d[v])
      d[v] = a[i]
    else:
      res.append(a[i])
  t = len(d)
  e = (t-1)*2
  if t == 1:
    return 0
  elif len(res) < e-t:
    return 'Impossible'
  else:
    res.sort()
    return sum(x for x in d.values()) + sum(res[:e-t])
  
print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])

        return self.__table[x]

    def root(self, x):
        return self.__root(x)

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[y] += self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g


@mt
def slv(N, M, A, XY):
    uf = UnionFind()

    for x, y in XY:
        uf.union(x, y)

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

    if len(d) == 1:
        return 0

    ans = 0
    n = []
    for v in d.values():
        m = min(v)
        ans += m
        v.remove(m)
        n.extend(v)

    e = len(d)-2
    if len(n) < e:
        return 'Impossible'

    n.sort()
    ans += sum(n[:e])
    return ans


def main():
    N, M = read_int_n()
    A = read_int_n()
    XY = [read_int_n() for _ in range(M)]
    print(slv(N, M, A, XY))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])

        return self.__table[x]

    def root(self, x):
        return self.__root(x)

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[y] += self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g


@mt
def slv(N, M, A, XY):
    uf = UnionFind()

    for x, y in XY:
        uf.union(x, y)

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

    for v in d.values():
        heapq.heapify(v)

    if len(d) == 1:
        return 0
    ans = 0
    n = []
    for v in d.values():
        ans += heapq.heappop(v)
        n.extend(v)

    e = len(d)-2
    n.sort()
    if len(n) < e:
        return 'Impossible'
    ans += sum(n[:e])
    return ans


def main():
    N, M = read_int_n()
    A = read_int_n()
    XY = [read_int_n() for _ in range(M)]
    print(slv(N, M, A, XY))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
X = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    X[a].append(b)
    X[b].append(a)

def col(n, E):
    C = [-1] * n
    c = 0
    for i in range(N):
        if C[i] >= 0: continue
        Q = [i]
        C[i] = c
        while Q:
            x = Q.pop()
            for y in E[x]:
                if C[y] == -1:
                    C[y] = C[x]
                    Q.append(y)
        c += 1
    return C

C = col(N, X)
K = max(C) + 1

if N < 2*K-2:
    print("Impossible")
elif K == 1:
    print(0)
else:
    B = [-1] * K
    BB = []
    for i in range(N):
        if B[C[i]] < 0:
            B[C[i]] = A[i]
        else:
            if A[i] >= B[C[i]]:
                BB.append(A[i])
            else:
                BB.append(B[C[i]])
                B[C[i]] = A[i]
    BB = sorted(BB)
    
    print(sum(B + BB[:K-2]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    k=n-m-1 # merge する回数
    if(k==0):
        print(0)
        return
    if(n<2*k):
        print("Impossible")
        return

    # cost の小さい方から使いたい
    A=[[a,i] for i,a in enumerate(map(int,input().split()))]
    A.sort()
    E=[[] for _ in range(n)]
    for _ in range(m):
        x,y=map(int,input().split())
        E[x].append(y)
        E[y].append(x)

    cnt=0
    col=[None]*n # 連結成分に分解
    def dfs(v)->bool:
        if(col[v] is not None): return False
        col[v]=cnt
        Q=[v]
        while(Q):
            v=Q.pop()
            for nv in E[v]:
                if(col[nv] is not None): continue
                col[nv]=cnt
                Q.append(nv)
        return True

    for v in range(n):
        cnt+=dfs(v)

    # 各連結成分(n-m 個)から1個ずつ選ぶ
    ans=0
    used=[0]*cnt
    for i in range(n):
        a,v=A[i]
        if(not used[col[v]]):
            ans+=a
            used[col[v]]=1
            A[i][0]=INF

    # 残りの頂点から 2k-(n-m) 個選ぶ
    A.sort()
    for a,v in A[:2*k-(n-m)]:
        ans+=a

    print(ans)
resolve()

Submission status: Accepted

Solution code:
from heapq import heappop
from collections import defaultdict

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]


N, M, *L = map(int, open(0).read().split())
A, XY = L[:N], L[N:]

uf = UnionFind(N)
for x, y in zip(*[iter(XY)] * 2):
    uf.union(x, y)

C = defaultdict(list)
for i, a in enumerate(A):
    C[uf.find(i)].append(a)

if len(C) < 2:
    print(0)
    quit()

D = [sorted(c) for c in C.values()]
s = sum(heappop(d) for d in D)

L = []
for d in D:
    L += d

if len(L) < len(D) - 2:
    print("Impossible")
else:
    print(s + sum(sorted(L)[:len(D) - 2]))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        self.group_num = n

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        self.group_num -= 1


n, m = LI()
A = [(a, i) for i, a in enumerate(LI())]
heapify(A)
uf = UnionFind(n)
for x, y in LIR(m):
    uf.union(x, y)

k = uf.group_num
if (k - 1) * 2 > n:
    print('Impossible')
else:
    ans = 0
    ret = 0
    ret2 = 0
    D = defaultdict(int)
    while ret + ret2 < (k - 1) * 2:
        a, i = heappop(A)
        r = uf.root(i)
        if not D[r]:
            D[r] = 1
            ret += 1
            ans += a
        else:
            if ret2 < (k - 1) * 2 - k:
                ret2 += 1
                ans += a
    print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [int(i) for i in input().split()]
xy = [[int(i) for i in input().split()] for _ in range(M)]

class UnionFind() :
    def __init__(self, N) :
        self.parent = [-1] * N
        
    def root(self, x) :
        while self.parent[x] >= 0:
            x = self.parent[x]
        return x

    def unite(self, x, y) :
        rx = self.root(x)
        ry = self.root(y)

        if rx != ry :
            if self.parent[rx] > self.parent[ry] :
                self.parent[rx] = ry
            else :
                if self.parent[rx] == self.parent[ry] :
                    self.parent[rx] -= 1
                self.parent[ry] = rx
    
    def same(self, x, y) :
        return self.root(x) == self.root(y)
        
    def size(self, x) :
        return -self.parent[self.root(x)]
        
UF = UnionFind(N)
for x, y in xy :
    UF.unite(x, y)

component = 0
for p in UF.parent :
    if p < 0 :
        component += 1
        
if N < 2 * (component - 1) :
    print('Impossible')
elif component == 1 :
    print(0)
else :
    ret = 0
    b = [(a[i], UF.root(i)) for i in range(N)]
    b.sort()
    visited = [False] * N
    c = component - 2
    for v, k in b :
        if not visited[k] :
            ret += v
            visited[k] = True
        elif c > 0 :
            ret += v
            c -= 1
            
    print(ret)

Submission status: Accepted

Solution code:
import heapq
from collections import deque


n, m = map(int, input().split())
a = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(m)]
tree = [[] for i in range(n)]

for b, c in info:
    tree[b].append(c)
    tree[c].append(b)

visited = [False] * n
group = []
for i in range(n):
    if visited[i]:
        continue
    q = deque([i])
    visited[i] = True
    tmp = [a[i]]
    while q:
        pos = q.pop()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            visited[next_pos] = True
            q.append(next_pos)
            tmp.append(a[next_pos])
    group.append(tmp)

for i in range(len(group)):
    group[i] = sorted(group[i])

ans = 0
cnt = len(group)*2 - 2

if cnt == 0:
    print(0)
    exit()
    
for i in range(len(group)):
    ans += group[i][0]
    cnt -= 1
    group[i][0] = 10**9 + 7

q = []
for i in range(len(group)):
    for num in group[i]:
        if num != 10**9 +7:
            heapq.heappush(q, num)

for i in range(cnt):
    if not q:
        print("Impossible")
        exit()
    ans += heapq.heappop(q)
print(ans)