Kruskal's algorithm finds the Minimum Spanning Tree using Union-Find:
Sort all edges by weight
For each edge in order, if it connects two different components, add it to MST
Stop when MST has edges
function kruskal(n, edges):
sort edges by weight // sort by weight
uf = new UnionFind(n)
mst = []
for each (u, v, weight) in edges:
if uf.union(u, v): // returns true if they were separate
mst.add((u, v, weight))
if mst.length == n - 1:
break
return mst
Time: for sorting, plus for union-find operations.
The cycle check (were they already connected?) is exactly what Union-Find provides efficiently.