Kruskal Algorithm — Minimum Spanning Tree
Practice this coding question on Coding Gurukul.
Problem statement
Given an undirected weighted graph, find the total weight of a minimum spanning tree using Kruskal’s algorithm. Sort edges by weight and use Disjoint Set Union to add edges that connect different components. If the graph is disconnected, print IMPOSSIBLE. A single vertex has answer 0. Negative weights, repeated edges and self-loops are allowed; do not include self-loops in the tree. Print only the total weight, using signed 64-bit arithmetic. Target O(m log m) time. Worked example The edges 0–1, 1–2 and 2–3 have weights 1, 2 and 3. They connect all four vertices with minimum total weight 6.
Input format
First line: n m. Next m lines: undirected edge u v w.
Output format
Print the minimum total cost, or IMPOSSIBLE.
Constraints
1 <= n <= 100000; 0 <= m <= 200000; 0 <= u,v < n; -10^9 <= w <= 10^9.
Sample input
4 5 0 1 1 1 2 2 2 3 3 0 3 10 0 2 8
Sample output
6
Sign in to run or submit a solution in C++, Java or Python.