Problem title
Avg time to solve

Find the Good Matrix
30 mins
Point to Greatest Value Node
10 mins
Check if the Word is present in Sentence or not
15 mins
Kth smallest node in BST
15 mins
Closest Binary Search Tree Value
15 mins
Add One to Linked List
10 mins
Exactly One Child
15 mins
Predecessor and Successor In BST
25 mins
Pair sum in a BST
15 mins
Sum Of K Smallest Elements In BST
15 mins

Minimum Spanning Tree

Difficulty: MEDIUM
Contributed By
Avg. time to solve
34 min

Problem Statement

You are given an undirected, connected and weighted graph G(V, E), consisting of V number of vertices (numbered from 0 to V-1) and E number of edges.

Find and print the total weight of the Minimum Spanning Tree (MST) using Kruskal's algorithm.

By definition, a minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Input Format :
The first input contains two integers, N and M, the number of vertices and edges in the graph respectively.

The next M input lines contains three integers X, Y and W each, representing each edge of the graph.

The edge X Y W represents an edge between vertices X and Y, having weight W.
The edges will be passed to the function as a array of arrays. Each array will contain 3 integers, X, Y, and W in that order.
Output Format :
Print the total weight of the minimum spanning tree.
You don't explicitly have to print anything, just return the total weight.
Constraints :
2 <= V <= 10^5
1 <= E <= 3 * 10^5
0 <= X < N
0 <= Y < N
1 <= W <= 10^4

where V and E represent the number of vertices and edges respectively.
X and Y represent the vertices between which there is an edge.
W is the weight of the edge.

Time limit: 1sec
Sample Input 1 :
4 4
0 1 3
0 3 5
1 2 1
2 3 8
Sample Output 1 :
Explanation for Sample Input 1:
The edge (2,3) having weight 8 will be excluded from the MST. The total weight of the MST then will be 1 + 3 + 5 = 9.
Sample Input 2:
4 4
1 2 6
2 3 2
1 3 2
1 0 2
Sample Output 2:
Reset Code
Full screen