Minimum Spanning Tree

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.

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

Kruskal's Algorithm

The algorithm first puts all vertices of the graph as a collection of single-vertex trees, separate from each other. Then, they are gradually combined together to form a single tree. Before the algorithm is executed, we first sort all edges of the graph in order of non-decreasing weights. Then we start selecting edges in the sorted order. If the ends of the currently selected edge belong to different subtrees, we will connect those subtrees, and that edge is added in the pool of edges of the MST.

After we've iterated through all the edges of the graph, all vertices will belong to the same subtree, which will be the MST.

Following are the steps to implement this algorithm:

Sort all edges of the graph in order of non-decreasing weights.
Put each vertex of the graph in their own tree, i.e. set the parent of each vertex to itself.
Iterate through all edges in the sorted order; if the two vertices of the edge belong to different subtrees, i.e. have different parents, add that edge to the MST and make the parents of each vertex in the two connected subtrees equal.
After the iterating through all the edges, you will end up having a collection of edges that will make up the MST.

How to find whether two vertices belong to different or the same subtrees?

There exists a beautiful data structure called Disjoint Set Union (DSU), which can manage sets efficiently. Using a DSU, we can find which element exists in which set and merge two sets as well. Initially, we assign each vertex a new set, represented by a set number, equal to the value of the vertex itself.

To find which subtree a vertex lies in, we simply check for the set number corresponding to that element in the DSU. If the set number does not match the vertex value of the element, we recursively check for the ‘set number’ itself, and we do this until (current value) ≠ (set number). When we terminate this algorithm, we actually reach the ‘head’ of the set.

To merge two sets, we simply point the head of the smaller set to the head of the larger set (Union By Rank). Hence, this is an O(1) operation.

If you notice, the worst case for a ‘find’ operation will be O(N). To avoid this scenario, we use an algorithm called Path Compression. Putting it briefly, suppose the heads of the sets point in this fashion:

1→2→3→4

If we want to look for the set number of 1, we have to reach 4. After we know that the set head is 4, we simply point all values encountered so far to 3, so it would look something like:

1→4←3

This is Path Compression in essence. It has an amortized (per operation analysis) constant time complexity.

Time Complexity

E and V are the numbers of edges and vertices in the graph respectively. O(E * log(E)) or O(E * log(V)) time is taken up to sort the edges.

We can replace E * log(E) with E * log(V) above because

E ≤ V * V

=> log(E) ≤ log(V^2)

=> log(E) ≤ 2 * log(V)

O(V) time is taken to initialize the parent of each vertex and O(E) time is taken to set the parents of each vertex in the two connected subtrees to be equal for all edges.

Therefore the overall time complexity is O(E * log(V))

Space Complexity

O(E) to store the edges and O(V) to store the parents of each vertex.

Therefore the overall space complexity is O(E + V).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation for Sample Input 1:

Sample Input 2:

Sample Output 2: