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:
N,M=map(int,input().split())
A=list(map(int,input().split()))
P=[i for i in range(N)]
size=[1 for i in range(N)]

def find(a):
    if a==P[a]:
        return a
    else:
        return find(P[a])
        
def union(b,c):
    B=find(b)
    C=find(c)
    if size[B]>=size[C]:
        P[C]=P[B]
        size[B]+=size[C]
    else:
        P[B]=P[C]
        size[C]+=size[B]
for i in range(M):
    x,y=map(int,input().split())
    if find(x)!=find(y):
        union(x,y)
        
p=[]
for i in range(N):
    p.append([A[i],find(P[i])])
#print(p)
p.sort()
ANS1=[]
ANS2=[]
d={}
for i in range(N):
    if p[i][1] in d:
        ANS2.append(p[i][0])
    else:
        d[p[i][1]]=1
        ANS1.append(p[i][0])
#print(ANS1,ANS2)
if (len(ANS1)+len(ANS1)-2)>N:
    print("Impossible")
elif len(ANS1)==1:
    print(0)
else:
    ANS=sum(ANS1)+sum(ANS2[:len(ANS1)-2])
    print(ANS)

Submission status: Accepted

Solution code:

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

class Uf:
    def __init__(self, N, mins):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N
        self.mins = mins
        self.amins = list(range(N))

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

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0

            if self.mins[v] > self.mins[u]:
                self.mins[v] = self.mins[u]
                self.amins[v] = self.amins[u]
            self.mins[u] = -1
            self.amins[u] = -1
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.mins[u] > self.mins[v]:
                self.mins[u] = self.mins[v]
                self.amins[u] = self.amins[v]
            self.mins[v] = -1
            self.amins[v] = -1

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

    def min(self, x):
        return self.mins[self.root(x)]

uf = Uf(N, A.copy())

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


mins = [x for x in uf.mins if x != -1]
amins = set([x for x in uf.amins if x != -1])
ans = sum(mins)
A = [a for i, a in enumerate(A) if i not in amins]
A.sort()
ntrees = len(mins)
if ntrees == 1:
    print(0)
    exit()
if ntrees * 2 - 2 > N:
    print("Impossible")
    exit()
ans += sum(A[:ntrees - 2])
print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)

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

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

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

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

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

for i in range(M):
    x, y = list(map(int, input().split()))
    uf.union(x, y)

D = defaultdict(list)
for i in range(N):
    D[uf.find(i)].append(a[i])

for i in D:
    D[i] = sorted(D[i])

ans = 0
Q = []

x = len(D)
for i in D:
    if len(D[i]) == 1:
        ans += D[i][0]
    else:
        ans += D[i][0]
        m = len(D[i])
        for j in range(1, m):
            heappush(Q, D[i][j])

if len(D) == 1:
    print(0)
else:
    if N >= 2 * len(D) - 2:
        for i in range(len(D) - 2):
            x = heappop(Q)
            ans += x
        print(ans)
    else:
        print("Impossible")

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
if M==N-1:
    print(0)
    exit()
if N<2*(N-M-1):
    print("Impossible")
    exit()
a=[int(i) for i in input().split()]
x=[0 for i in range(M)]
y=[0 for i in range(M)]
for i in range(M):
    x[i],y[i]=map(int,input().split())
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)
init(N)
for i in range(M):
    unite(x[i],y[i])
A=[find(i) for i in range(N)]
K=0
D=dict()
for i in range(N):
    if A[i] in D:
        D[A[i]].append((a[i],i))
    else:
        D[A[i]]=[(a[i],i)]
        K+=1
ans=0
used=[0 for i in range(N)]
for i in D:
    seq=min(D[i])
    ans+=seq[0]
    used[seq[1]]=1
q=[]
for i in range(N):
    if used[i]==0:
        heapq.heappush(q,(a[i],i))
for _ in range(2*(N-M-1)-K):
    s,t=heapq.heappop(q)
    ans+=s
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
if N-1==M:
  print(0)
  exit()
A=[int(a) for a in input().split()]
G=[[] for i in range(N)]
inf=float("inf")
for i in range(M):
  a,b=map(int,input().split())
  G[a].append(b)
  G[b].append(a)
Tree=[-1]*N

def BFS(x,n):
  global Tree
  stack=deque([x])
  while stack:
    a=stack.popleft()
    Tree[a]=n
    for b in G[a]:
      if Tree[b]<0:
        stack.append(b)
n=0
for i in range(N):
  if Tree[i]<0:
    BFS(i,n)
    n+=1
    
P=[inf]*n
for i in range(N):
  P[Tree[i]]=min(P[Tree[i]],A[i])
P.sort()
ans=sum(P)
P.append(inf)
k=0
A.sort()
for i in range(N):
  if A[i]==P[k]:
    A[i]=inf
    k+=1
A.sort()
if 2*(N-M-1)-n>=N or n>2*(N-M-1) or N-2*(N-M-1)<0:
  print("Impossible")
  exit()
for i in range(2*(N-M-1)-n):
  ans+=A[i]
if ans!=inf:
  print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush


def solve():
    N, M = map(int, input().split())
    a = list(map(int, input().split()))

    if M == N - 1:
        ans = 0
    elif 2 * (N - M - 1) > N:
        ans = 'Impossible'
    else:
        g2i = [[i] for i in range(N)]
        i2g = list(range(N))

        def merge(ia, ib):
            # print(g2i, i2g, ia, ib)
            if len(g2i[i2g[ia]]) < len(g2i[i2g[ib]]): ia, ib = ib, ia
            ga, gb = i2g[ia], i2g[ib]
            for j in g2i[gb]: i2g[j] = ga
            g2i[ga].extend(g2i[gb])
            g2i[gb] = []

        for _ in range(M):
            tx, ty = map(int, input().split())
            merge(tx, ty)

        ans = 0
        need = 2 * (N - M - 1)
        rest = []
        for gi in range(len(g2i)):
            t = []
            for i in g2i[gi]:
                t.append(a[i])
            if not t: continue
            heapify(t)
            ans += heappop(t)
            need -= 1
            rest += t
        ans += sum(sorted(rest)[:need])

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    def find(self,x):#親を探す
        if self.par[x] ==x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self,x,y):#x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
from collections import defaultdict
from heapq import heapify,heappop
import sys
N,M = map(int,input().split())
tree = Unionfindtree(N)
A = [int(i) for i in input().split()]
table=[]
for i in range(M):
    x,y=map(int,input().split())
    tree.union(x,y)

dd=defaultdict(list)
for i in range(N):
    dd[tree.find(i)].append(A[i])
ans=0
g=0
for s in dd.keys():
    heapify(dd[s])
    ans+=heappop(dd[s])
    g+=1
if g==1:
    print(0)
    sys.exit()
if g==2:
    print(ans)
    sys.exit()
L=[]
for s in dd.values():
    L+=list(s)
L.sort()
if len(L)<g-2:
    print('Impossible')
    sys.exit()

ans+=sum(L[:g-2])
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = list(map(int, input().split()))
par = list(range(N))

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def unite(x, y):
    x, y = root(x), root(y)
    if x != y:
        par[y] = x

for _ in range(M):
    unite(*map(int, input().split()))

group = {i: [] for i in range(N)}
for i in range(N):
    group[root(i)].append((a[i], i))
ans = 0
cnt = 2 * (N - M - 1)
if N < cnt:
    print('Impossible')
    exit()
elif cnt == 0:
    print(0)
    exit()

visited = set()
for g in group.values():
    if g:
        c, i = min(g)
        ans += c
        cnt -= 1
        visited.add(i)

for v, i in sorted((v, i) for i, v in enumerate(a)):
    if cnt > 0 and i not in visited:
        ans += v
        visited.add(i)
        cnt -= 1
print(ans)

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
par,rank,b,t = [i for i in range(n)],[0 for i in range(n)],[],n-m-1
def root(x):
	if par[x]!=x: par[x] = root(par[x])
	return par[x]
def unite(x,y):
	x2,y2 = root(x),root(y)
	if x2!=y2:
		if rank[x2]<rank[y2]: par[x2] = y2
		else: par[y2] = x2
		if rank[x2]==rank[y2]: rank[x2]+=1
for _ in range(m):
	x,y = (int(i) for i in input().split())
	unite(x,y)
for i in range(n): par[i] = root(par[i])
if n<2*t: ans = "Impossible"
elif t==0: ans = 0
else:
	for i in range(n): b.append((a[i],par[i]))
	ans,b,v,w = 0,sorted(b),[1]*n,n-m-2
	for i,j in b:
		if v[j]: v[j],ans = 0,ans+i
		elif w: w,ans = w-1,ans+i
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

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


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

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

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

        if x == y:
            return

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

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

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    UF.union(x, y)

UF.all_find()

# グループに分解
D = defaultdict(list)
for i in range(N):
    D[UF.par[i]].append(A[i])

# グループ数
group = len(D)
if group == 1:
    print(0)
    exit()

# 優先度付きキュー
for key in D.keys():
    heapq.heapify(D[key])

# 各グループから最低1つは選ぶ必要がある
ans = 0
for key in D.keys():
    ans += heapq.heappop(D[key])

# 残り物から小さい順に足りない分を補充（必要な辺の数: group-1, 必要な頂点数2*group-2, 不足分group-2)
remain = []
for value in D.values():
    remain.extend(value)

remain.sort()
if len(remain) < group - 2:
    print("Impossible")
else:
    ans += sum(remain[:group - 2])
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
A = [int(x) for x in input().split()]


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if 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

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


if 2 * (N - M - 1) > N:
    print('Impossible')
elif N - M == 1:
    print(0)
else:
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(int, input().split())
        uf.union(x, y)

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

    ans = 0
    rest = []
    for v in tree.values():
        x = min(v)
        v.remove(x)
        rest += v
        ans += x

    rest = sorted(rest)
    ans += sum(rest[:N - M - 2])
    print(ans)

Submission status: Accepted

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()
  if M == N-1:
    print(0); exit()

  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) * 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; self.rank = [0] * n
  def __repr__(self): return "union_find({0})".format([self.root(i) for i in range(n)])
  def unite(self, x, y):
    x = self.root(x); y = self.root(y)
    if x == y: return
    if self.rank[x] < self.rank[y]: self.par[x] = y
    else:
      self.par[y] = x
      if self.rank[x] == self.rank[y]: self.rank[x] += 1
  def 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: Accepted

Solution code:
import sys
from collections import defaultdict

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

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

  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1<root2:
      self.table[root1]+=self.table[root2]
      self.table[root2]=root1
    else:
      self.table[root2]+=self.table[root1]
      self.table[root1]=root2

N,M=map(int,input().split())
A=[int(i) for i in input().split()]
uf=UnionFind(N)
for i in range(M):
  x,y=map(int,input().split())
  uf.union(x,y)
groups=defaultdict(list)
for j in range(N):
  groups[uf.find(j)].append(A[j])

groups = [sorted(g, reverse=True) for g in groups.values()]

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

ans=0
cnt=[]
for group in groups:
  ans+=group.pop()
  cnt+=group

if len(groups)-2 > len(cnt):
  print("Impossible")
else:
  cnt.sort()
  ans+=sum(cnt[:len(groups)-2])
  print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
import heapq

N,M=map(int, raw_input().split())
cost=map(int, raw_input().split())

par=[i for i in range(N)]

def root(x):
	if par[x]==x:
		return x
	else:
		r=root(par[x])
		par[x]=r
		return r

def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y: return
	par[x]=y


for i in range(M):
	x,y=map(int,raw_input().split())
	unite(x,y)


group_cost=defaultdict(lambda: [])

for i in range(N):
	root(i)
	group_cost[par[i]].append(cost[i])


H = []

ans=0
for v in group_cost.values():
	v=sorted(v)
	ans+=v[0]
	H.append(v[1:])

nokori_cost=list(heapq.merge(*H))


if N < 2*(N-M-1):
	print "Impossible"
elif M == N-1:
	print 0
else:
	ans += sum(nokori_cost[:2*(N-M-1) - len(group_cost.keys())])
	print ans

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
import heapq

N,M=map(int, raw_input().split())
cost=map(int, raw_input().split())

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

nl=[ [] for i in range(N) ]

for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x].append(y)
	nl[y].append(x)


d=[ None for i in range(N) ]
V=[ None for i in range(N) ]

group_cost=defaultdict(lambda: [])

def dfs(start):
	q = deque([]) 
	V[start]=start
	d[start]=0
	heapq.heappush(group_cost[start],cost[start])
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i] is None:
				V[i]=start
				q.append(i)
				heapq.heappush(group_cost[start],cost[i])

for i in range(N):
	if V[i] is None:
		dfs(i)


H = []

ans=0
for v in group_cost.values():
	v=sorted(v)
	ans+=v[0]
	H.append(v[1:])

nokori_cost=list(heapq.merge(*H))


if N < 2*(N-M-1):
	print "Impossible"
elif M == N-1:
	print 0
else:
	ans += sum(nokori_cost[:2*(N-M-1) - len(group_cost.keys())])
	print ans

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify, nsmallest

N, M = map(int, input().split())
costs = list(map(int, input().split()))
treemin = [(cost, i) for i, cost in enumerate(costs)] # グループ内での最小値

parent = list(range(N))
rank = [0] * (N)
def getRoot(x):
  if parent[x] == x:
    return x
  else:
    # ルートに繋ぎ変える
    parent[x] = getRoot(parent[x])
    return parent[x]

def unite(x, y):
  global treemin
  xRoot = getRoot(x)
  yRoot = getRoot(y)
  if xRoot == yRoot:
    return
  if rank[xRoot] < rank[yRoot]:
    parent[xRoot] = yRoot
    if treemin[yRoot][0] > treemin[xRoot][0]:
      treemin[yRoot] = treemin[xRoot]
  else:
    parent[yRoot] = xRoot
    if treemin[xRoot][0] > treemin[yRoot][0]:
      treemin[xRoot] = treemin[yRoot]
    if rank[xRoot] == rank[yRoot]:
      rank[xRoot] += 1

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

ans = 0
numtree = 0
exclude = set()
for i in range(N):
  if parent[i] == i:
    numtree += 1
    ans += treemin[i][0]
    exclude.add(treemin[i][1])

if N < (numtree-1) * 2:
  print('Impossible')
  exit()
if numtree == 1:
  print(0)
  exit()

heap = []
for i in range(N):
  if i not in exclude:
    heappush(heap, costs[i])

ans += sum(nsmallest(numtree - 2, heap))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
from heapq import merge
import sys
sys.setrecursionlimit(10**7)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)] # [next, rank]
 
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)
 
D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])
 
H = []
res = 0 

for k, v in D.items():
    v = sorted(v)
    res += v[0]
    H.append(v[1:])
 
if N < 2*(N-M-1):
    print("Impossible")
elif M == N-1:
    print(0)
else:
    res += sum(list(merge(*H))[:2*(N-M-1) - len(D.keys())])
    print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)] # [next, rank]
 
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)
 
D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])
 
H = []
res = 0 

for k, v in D.items():
    v = sorted(v)
    res += v[0]
    H.extend(v[1:])
 
if N < 2*(N-M-1):
    print("Impossible")
elif M == N-1:
    print(0)
else:
    res += sum(sorted(H)[:2*(N-M-1) - len(D.keys())])
    print(res)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
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):
        mins[uf.find(i)].append(a[i])
    if len(mins) == 1:
        return 0
    ans = 0
    others = []
    for v in mins.values():
        v.sort(reverse=True)
        ans += v.pop()
        others += v
    others.sort()
    return 'Impossible' if len(others) < len(mins) - 2 else ans + sum(others[:len(mins) - 2])

print(main())

Submission status: Accepted

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):
        mins[uf.find(i)].append(a[i])
    if len(mins) == 1:
        return 0
    ans = 0
    others = []
    for v in mins.values():
        v.sort(reverse=True)
        ans += v.pop()
        others += v
    others.sort()
    return 'Impossible' if len(others) < len(mins) - 2 else ans + sum(others[:len(mins) - 2])

print(main())

Submission status: Accepted

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

if M == N-1:
    print(0)
    exit()
if M + N//2 < N-1:
    print('Impossible')
    exit()

parent = [i for i in range(N)]
rank = [0] * N
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    else:
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1

for a,b in es:
    unite(a,b)
trees = {}
for i in range(N):
    trees[root(i)] = False

costs = []
for i,c in enumerate(src):
    costs.append((c,i))
costs.sort()

used = [False] * N
ans = used_n = 0
for c,v in costs:
    t = root(v)
    if trees[t]:
        continue
    else:
        trees[t] = used[v] = True
        used_n += 1
        ans += c

for c,v in costs:
    if used_n == 2*(N-M-1): break
    if used[v]: continue
    used_n += 1
    ans += c
print(ans)

Submission status: Accepted

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

if M == N-1:
    print(0)
    exit()
if M + N//2 < N-1:
    print('Impossible')
    exit()

parent = [i for i in range(N)]
rank = [0] * N
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    else:
        parent[rb] = ra
        if rank[ra] == rank[rb]: rank[ra] += 1

for a,b in es:
    unite(a,b)
trees = {}
for i in range(N):
    root(i)
for i in range(N):
    trees[root(i)] = False

costs = []
for i,c in enumerate(src):
    costs.append((c,i))
costs.sort()

used = [False] * N
ans = used_n = 0
for c,v in costs:
    t = root(v)
    if trees[t]:
        continue
    else:
        trees[t] = used[v] = True
        used_n += 1
        ans += c

for c,v in costs:
    if used_n == 2*(N-M-1): break
    if used[v]: continue
    used_n += 1
    ans += c
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

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 subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n,m = LI()
    a = LI()
    uf = UnionFind(n)
    for _ in range(m):
        x,y = LI()
        uf.union(x,y)

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

    l = len(d)
    if l == 1:
        return 0
    r = 0
    b = []
    for v in d.values():
        v.sort()
        r += v[0]
        b += v[1:]
    b.sort()
    if l % 2 == 0:
        ll = (l // 2 - 1) * 2
    else:
        ll = (l // 2 - 1) * 2 + 1
    if len(b) < ll:
        return 'Impossible'
    r += sum(b[:ll])
    return r



print(main())

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
from heapq import heapify, heappop, merge, heapreplace


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * 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 find(self, x, y):
        return self._root(x) == self._root(y)

    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
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def solve(aa, uft):
    roots = defaultdict(list)
    for x, a in enumerate(aa):
        roots[uft._root(x)].append(a)
    if len(roots) == 1:
        return 0
    if n < (len(roots) - 1) * 2:
        return 'Impossible'
    ans = 0
    queue = []
    for l in roots.values():
        l.sort()
        ans += l[0]
        queue.append(l[1:])
    lm = n - m - 2
    if lm > 0:
        mm = merge(*queue)
        for _ in range(lm):
            ans += next(mm)
    return ans


n, m = map(int, input().split())
aa = list(map(int, input().split()))
uft = UnionFind(n)
for _ in range(m):
    uft.union(*map(int, input().split()))
print(solve(aa, uft))