Given a weighted undirected graph, find the minimum spanning tree (MST) using Kruskal's algorithm. Return the total weight of the MST.
Input: n=4, edges=[[0,1,10],[0,2,6],[0,3,5],[1,3,15],[2,3,4]] → MST weight=19Input: n=3, edges=[[0,1,1],[1,2,2],[0,2,4]] → MST weight=3
Sort edges by weight. Use Union-Find: add an edge to MST if it connects two different components.
- Sort edges by weight (ascending).
- For each edge (u,v,w): if find(u) != find(v): add to MST (totalWeight += w), union(u,v).
- Stop when MST has n-1 edges.
import java.util.*;
class Solution {
int[] parent, rank;
public int kruskalMST(int n, int[][] edges) {
parent = new int[n]; rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
Arrays.sort(edges, (a,b)->a[2]-b[2]);
int total = 0, edgesUsed = 0;
for (int[] e : edges) {
if (edgesUsed == n-1) break;
int pu=find(e[0]), pv=find(e[1]);
if (pu != pv) {
if (rank[pu] < rank[pv]) parent[pu]=pv;
else if (rank[pu] > rank[pv]) parent[pv]=pu;
else { parent[pv]=pu; rank[pu]++; }
total += e[2]; edgesUsed++;
}
}
return total;
}
private int find(int x) { return parent[x]==x?x:(parent[x]=find(parent[x])); }
}
- Time Complexity: O(E log E)
- Space Complexity: O(V)