Edges in sorted order
Kruskal builds a minimum spanning tree by considering edges from cheapest to most expensive. It adds an edge only if its two endpoints currently belong to different components, since joining the same component would create a cycle.
Union find
The cycle check needs to ask whether two nodes are already connected. A disjoint set structure answers this efficiently. Each node points toward a representative of its component. Two optimizations make it nearly constant time:
- Path compression flattens chains during lookups.
- Union by rank attaches the smaller tree under the larger.
The flow is: sort edges, then for each edge find the representatives of both endpoints; if they differ, union them and keep the edge.
Key idea
Kruskal sorts edges and greedily keeps the cheapest that joins two separate components, using a union find structure with path compression and union by rank to test connectivity almost instantly.