191. Minimum Spanning Tree Weight

Given a connected undirected weighted graph with n vertices and m edges (each u, v, weight), find the total weight of its minimum 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 a single integer - the total weight of the minimum spanning tree.

1 <= n <= 10^5

A minimum spanning tree always has EXACTLY (n-1) edges for a connected graph with n vertices - if fewer edges end up added, the graph wasn't actually fully connected to begin with.

Find the total weight of the cheapest way to connect all vertices of a graph using a subset of its edges. Brute force: Try every possible subset of edges that connects all vertices, and find the one with minimum total weight - this is combinatorially expensive (choosing n-1 edges out of m), impractical for larger graphs. Optimised: Both Prim's and Kruskal's exploit the 'cut property' of minimum spanning trees (the cheapest edge crossing any partition of vertices is always safe to include) - Prim's applies this by growing outward from a single vertex, while Kruskal's applies it by processing edges globally in weight order, and both provably reach the same minimum total weight.

Sort all m edges by weight ascending. Process them in that order, and for each edge, run a fresh DFS or BFS over the edges already accepted into the growing tree to check whether the edge's two endpoints are already connected; if they are not connected, accept the edge and add its weight to the running total. Because connectivity is re-verified via a full traversal of the tree built so far for every candidate edge, this is far slower than necessary. Time: O(m * (n + m)) Space: O(n + m)

Sort all m edges by weight ascending in O(m log m). Maintain a disjoint-set-union structure over the n vertices with union-by-rank and path compression, and process edges in increasing weight order, using near-constant-time find operations to check whether an edge's two endpoints are already in the same component; whenever they are not, union the components and add the edge's weight to the running total, stopping once n-1 edges have been accepted. The union-find operations run in effectively O(alpha(n)) amortized time each, so the overall cost is dominated by the initial sort. Time: O(m log m) Space: O(n + m)

Maintain a 'key' value for every vertex (the cheapest known edge weight connecting it to the growing tree) and a visited flag. Starting from any vertex, repeatedly scan all n vertices to find the unvisited vertex with the smallest key, mark it visited, add its key to the MST total, and relax the keys of its neighbors. Because the minimum-key vertex is found by a plain linear scan each round instead of a heap, each of the n rounds costs O(n), which is fine for dense graphs but wasteful for the sparse graphs typical at this scale. Time: O(n^2) Space: O(n + m)

1. PRIM'S approach: grow a tree from any starting vertex, always adding the CHEAPEST edge that connects a new vertex to the growing tree - a min-heap of candidate edges makes this efficient. 2. KRUSKAL'S approach (equally valid): sort ALL edges by weight, and greedily add each one that doesn't create a cycle, using a union-find structure to check that quickly. 3. Either approach arrives at the same total minimum spanning tree weight.

Time: O(m log n) for either algorithm - Prim's with a min-heap, or Kruskal's with sorting plus union-find. Space: O(n + m), for the heap/sorted edges and the tree/union-find structure.

n = 1 (no edges needed, weight 0), multiple edges of equal weight, and n at its maximum of 10^5 to confirm Prim's/Kruskal's runs efficiently.

Be ready to discuss when to prefer one algorithm over the other: Kruskal's tends to be simpler when edges are already sorted or the graph is sparse, while Prim's (with a heap) can be more efficient for DENSE graphs with many edges relative to vertices.