Hard · Kruskal + Union-Find
Understand → Visualise → Practice.
A minimum spanning tree connects every vertex with n − 1 edges and the least possible total cost. Kruskal processes edges from cheapest to most expensive.
Union–find answers whether an edge's endpoints are already connected; accept only edges joining different components.
Increasing cost makes the greedy choice safe.
Same root means the edge would create a cycle.
Merge different components until n − 1 edges are used.
O(E log E) time for sorting and nearly O(1) amortised union–find operations; O(V) space.
A graph that never reaches n − 1 accepted edges is disconnected and has no spanning tree.
Read the full guides first: Binary Trees and Traversals, Binary Search Trees, Graphs, BFS and DFS, Weighted Graphs, Dijkstra and Union–Find.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.