385. Kruskal's Algorithm - MST Edges

Given a connected undirected weighted graph with n vertices (0-indexed) and m edges (each u, v, weight), run Kruskal's algorithm: process edges in ascending order of weight (ties broken by smaller u, then smaller v), adding an edge to the spanning tree only if its endpoints aren't already connected by previously-added edges. Print each added edge as 'u v', in the order Kruskal's algorithm adds them, followed by a final line with the total weight of the spanning tree.

Input: The first line contains an integer n, the number of vertices. The second line contains an integer m, the number of edges. Each of the next m lines contains three space-separated integers u, v, and weight. Output: Print each edge added to the spanning tree as 'u v', one per line in the order Kruskal's algorithm adds them, followed by a final line with the total spanning tree weight.

1 <= n <= 10^5

This is the natural sibling to Prim's algorithm for the same underlying MST problem - Kruskal's processes edges GLOBALLY by weight, while Prim's grows a single tree outward from one vertex; both are provably optimal, just organized differently.

Build a minimum spanning tree by processing edges in ascending weight order, adding each one that doesn't create a cycle. Brute force: Try every possible subset of (n-1) edges and check if it forms a valid, minimum-weight spanning tree - this is combinatorially expensive, when the greedy sorted-edge-processing approach directly produces the correct minimum. Optimised: Processing edges in ascending weight order and using UNION-FIND to instantly check 'would this edge create a cycle' (in near-O(1) amortized time) lets Kruskal's greedily build the minimum spanning tree in a single pass over the sorted edges - the greedy choice (always take the cheapest non-cycle-creating edge) is provably optimal.

Sort all edges by weight (ties by smaller u then smaller v). For each edge in that order, run a fresh BFS or DFS over the edges added so far to check whether u and v already belong to the same component; if not, add the edge to the spanning tree. This works because Kruskal's greedy rule is simply to skip edges that would create a cycle, and a traversal is a valid (if slow) way to test that. Since the growing forest never has more than n-1 edges, each connectivity check costs O(n), making this correct but wasteful. Time: O(m log m + m*n) Space: O(n + m)

Use a Disjoint Set Union structure with both union by rank/size and path compression (every node visited during a find gets re-pointed directly to the root). This makes each find/union pair run in amortized O(alpha(n)) time, the inverse Ackermann function, which is effectively constant for any n up to 10^5. The total cost is then dominated purely by sorting the edges, giving the fastest practical implementation of Kruskal's algorithm while still producing edges in the exact required order. Time: O(m log m) Space: O(n)

Replace the traversal check with a Disjoint Set Union structure, but only apply the union-by-rank/size heuristic (always attach the smaller tree under the bigger one) without path compression. This guarantees every tree has height O(log n), so each find operation costs at most O(log n) instead of an O(n) traversal. Processing all m sorted edges this way costs O(m log n), which combined with the O(m log m) sort is a real asymptotic improvement over the brute-force traversal approach. Time: O(m log m) Space: O(n)

1. Sort ALL edges by (weight, u, v) ascending - this fixes the exact processing order. 2. Use UNION-FIND: process each sorted edge, adding it to the answer only if its two endpoints are CURRENTLY in DIFFERENT sets (meaning adding it wouldn't create a cycle), then UNION those sets together. 3. Continue through all sorted edges; the added edges (in order) and their total weight are the final answer.

Time: O(m log m), dominated by sorting the edges - the union-find operations afterward are nearly O(1) amortized each. Space: O(n + m), for the union-find structure and the sorted edge list.

multiple edges of equal weight requiring the tie-break by smaller u then smaller v, n = 1 (no edges added, weight 0), and n at its maximum of 10^5 to confirm the union-find approach runs efficiently.

Be ready to explain that the SPECIFIC parent-pointer choices inside your union-find implementation don't affect WHICH edges get added or their order - only the fixed sorted edge order and the connectivity check do, making the output fully deterministic regardless of implementation details like path compression or union-by-rank specifics.