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
def kruskal(n, edges):
edges.sort(key=lambda e: e[2]) # sort by weight
uf = UnionFind(n)
mst = []
for u, v, weight in edges:
if uf.union(u, v): # returns True if they were separate
mst.append((u, v, weight))
if len(mst) == 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.