String Coding Problems

Arrays Coding Problems

Sorting Coding Problems

Searching Coding Problems

Coding Algorithms

Tree Coding Problems

Stack Coding Problems

Linked list Coding Problems

Graph Coding Problems

Greedy Algorithms Coding Problems

Dynamic Programming Coding Problems

Matrix Coding Problems

Recursion Coding Problems

Number Theory Coding Problems

Backtracking Coding Problems

Heap Coding Problems

Brute Force Coding Problems

Implementation Coding Problems

Google Contests

Competitive Programming Coding


Minimum Spanning Tree

Minimum Spanning Tree: This problem has been asked in interview/coding rounds of many top tech companies such as Amazon, Samsung, Flipkart, Microsoft etc.
Submitted by Divyansh Jaipuriyar, on June 16, 2020

Problem statement

Given a weighted undirected graph. Find the sum of weights of edges of a Minimum Spanning Tree.


Given 2 integers N and M. N represents the number of vertices in the graph. M represents the number of edges between any 2 vertices.

Then M lines follow, each line has 3 space-separated integers a, b, w. Where, a and b represents an edge from a vertex a to a vertex b and w represents the weight of that edge.


Print the summation of edges weights in the MST.


N = 4, M = 5
    1 2 7
    1 4 6
    4 2 9
    4 3 8
    2 3 6

19, is the sum of edges of MST.

Solution Approach

The problem can be solved with the help of Kruskal and Prim's Algorithm of the minimum spanning tree.

Kruskal Algorithm: Kruskal's algorithm follows the greedy approach in each iteration it adds the weight of the minimum edge to a growing spanning tree.

Following steps are used in Kruskal algo,

  • Sort the graph edges on the basis of their weight.
  • Add only those edge which doesn't form cycle from minimum weight to maximum edge weight.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// edge structure for storing edge values.
struct edge {
    ll a, b, w;

// declare arr with maximum size.
edge arr[100005];

// declare parent array.
ll par[100005];

// declare find function to find.
// parent of current node.
ll find(ll x)
    // if par[x]==-1 then it is parent.
    if (par[x] == -1)
        return x;
        return par[x] = find(par[x]); // path compression.

// declare comp function which will help.
// to sort in according to min weight.
bool comp(edge a, edge b)
    if (a.w < b.w)
        return true;
        return false;

// if a and b are with different then.
// join them.
void union1(ll a, ll b)
    par[b] = a;

int main()
    cout << "Enter N and M: ";
    ll n, m;
    cin >> n >> m;

    for (ll i = 1; i <= n; i++)
        par[i] = -1;

    cout << "Enter edge and weights:\n";
    for (ll i = 0; i < m; i++) {
        cin >> arr[i].a >> arr[i].b >> arr[i].w;

    // initially sum variable as 0.
    ll sum = 0;
    // sort according to weight.
    sort(arr, arr + m, comp);
    for (ll i = 0; i < n; i++) {
        ll a = arr[i].a;
        ll b = arr[i].b;
        a = find(a);
        b = find(b);
        // check if they are already joined.
        if (a != b) {
            sum += arr[i].w;
            union1(a, b);
    cout << "Final sum: ";
    cout << sum << "\n";
    return 0;


Enter N and M: 4 5
Enter edge and weights:
1 2 7
1 4 6
4 2 9
4 3 8
2 3 6
Final sum: 19
  • Time Complexity in worst case is: (nlog(n))
  • Space Complexity in worst case is: O(n)

Problem reference: https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/practice-problems/algorithm/minimum-spanning-tree-5/

Comments and Discussions!

Load comments ↻

Copyright © 2024 www.includehelp.com. All rights reserved.