Problem p03440 (python)

Fixed submission:
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

Buggy submission (verdict: Runtime Error):
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)

edges=(N-M-1)*2

ans=0
for i in group_cost.keys():
	ans+=heapq.heappop(group_cost[i])
	edges-=1


nokori_cost=[]
if edges==0:
	print ans
	quit()
else:
	nokori_cost=heapq.merge(*group_cost.values())

	if len(list(nokori_cost))<edges:
		print "Impossible"
		quit()

	for i in range(edges):
		ans+=heapq.heappop()
	print ans

Buggy submission (verdict: Runtime Error):
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)


edges=(N-M-1)*2

ans=0
for i in group_cost.keys():
	ans+=heapq.heappop(group_cost[i])
	edges-=1

nokori_cost=[]
if edges==0:
	print ans
	quit()
else:
	nokori_cost=heapq.merge(*group_cost.values())

	if len(nokori_cost)<edges:
		print "Impossible"
		quit()

	for i in range(edges):
		ans+=heapq.heappop()
	print ans

Buggy submission (verdict: Runtime Error):
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])

while None in V:
	i=V.index(None)
	dfs(i)



edges=(N-M-1)*2

ans=0
for i in group_cost.keys():
	ans+=heapq.heappop(group_cost[i])
	edges-=1

nokori_cost=[]
if edges==0:
	print ans
	quit()
else:
	nokori_cost=heapq.merge(*group_cost.values())

	if len(nokori_cost)<edges:
		print "Impossible"
		quit()

	for i in range(edges):
		ans+=heapq.heappop()
	print ans

Buggy submission (verdict: Runtime Error):
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])

while None in V:
	i=V.index(None)
	dfs(i)


edges=(N-M-1)*2

ans=0
for i in group_cost.keys():
	ans+=heapq.heappop(group_cost[i])
	edges-=1

nokori_cost=[]
if edges==0:
	print ans
	quit()
else:
	for i in group_cost.values():
		nokori_cost+=i

	if len(nokori_cost)<edges:
		print "Impossible"
		quit()

	for i in range(edges):
		ans+=heapq.heappop()
	print ans