maximum-spanning-tree

Russian Translation Available

You are given a weighted graph with N vertices and M edges. Find the total weight of its maximum spanning tree.

Input

The first line contains one integer T denoting the number of test cases.
Each test case starts with a line containing 2 space-separated integer: N and M. Each of the following M lines contain description of one edge: three different space-separated integers: a,  b and c. a and b are different and from 1 to N each and denote numbers of vertices that are connected by this edge. c denotes weight of this edge.

Output

For each test case output one integer - the total weight of its maximum spanning tree.

Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 5000
1 ≤ M ≤ 100 000
1 ≤ c ≤ 10 000

SAMPLE INPUT
1
3 3
1 2 2
2 3 3
1 3 4

SAMPLE OUTPUT
7

Source: hackerearth | Difficulty: EASY


Solutions:
t=eval(input())
def root(x):
	while l1[x]!=x:
		l1[x]=l1[l1[x]]
		x=l1[x]
	return x
def union(x,y):
	global l1
	p=root(x)
	q=root(y)
	l1[p]=l1[q]
def kruskal():
	t=0
	for i in sorted(G,key=lambda x:x[0]):
		x=i[1][0]
		y=i[1][1]
		c=i[0]
		if root(x)!=root(y):
			
			t+=c
			union(x,y)
	return t         
while t!=0:
	
 n,m=list(map(int,input().split()))
 l=[]
 l1=["a"]*(n+1)
 for i in range(1,n+1):
	l1[i]=i
 G=[]
 for i in range(m):
	a,b,c=list(map(int,input().split()))
	c=c*-1
	#M[a].append(b)
	#M[b].append(a)
	G.append([c,(a,b)])
	#G.append([c,(b,a)])
 print(kruskal()*(-1))
 t-=1   
	




import sys as s
import heapq
INF = 1 + 25 * 10**8
def Prim(G, n, s):
	#dist = [INF] * (n+1)
	marked=[False]*(n+1)
	#dist[s] = 0
	mst=0
	
	heap = []
	heapq.heappush(heap, (0,s))

	while heap:
		d, u = heapq.heappop(heap)
		if marked[u]== True:
			continue#The continue statement, also borrowed from C, continues with the next iteration of the loop
		#if marked[u]==False:
		marked[u]=True  
		mst+=d  

		for (v, w) in G[u]:
			if marked[v]==False:
				#dist[v] = dist[u] + w
				heapq.heappush(heap, (w, v))

	return mst

t=eval(input())
while t!=0:
 n, m = list(map(int, s.stdin.readline().split()))
 G = [[] for i in range(n+1)]

 for i in range(m):
	x, y, z = list(map(int, s.stdin.readline().split()))
	z=z*(-1)
	G[x].append((y, z))
	G[y].append((x, z))
 print(Prim(G,n,1)*(-1))
 t-=1  



import collections
import heapq

def mst(graph, n):
	total = 0
	seen = set([1])
	q = graph[1]
	heapq.heapify(q)
	while q:
		cost, node = heapq.heappop(q)
		if node in seen: continue
		seen.add(node)
		total += cost
		if len(seen) == n: break
		for child in graph[node]:
			heapq.heappush(q, child)
	return total

def solve(n, mss):
	graph = collections.defaultdict(list)
	for a, b, cost in mss:
		graph[a].append((-cost, b))
		graph[b].append((-cost, a))
	mini = mst(graph, n)
	return -mini

if __name__ == '__main__':
	for _ in range(int(input())):
		n, m = list(map(int, input().split()))
		mss = [list(map(int, input().split())) for _ in range(m)]
		print(solve(n, mss))