Kruskal Minimum Spanning Tree, is a Graphs related problem and in this post we will see how we can solve this challenge in C++

Kruskal's Minimum spanning tree:

till V-1 edges are there:

  1. pick the smallest weight edge

  2. check if on adding it can cause a cycle or not to the existing edges in MST

  3. repeat step 2

    TC: O(ElogE) sorting + O(ElogV) union operation

    Here we do union by rank and root finding by path compression

Please check the main.cpp snippet for the solution.

This solution originally posted at: Github by @susantabiswas