Kruskal's Algorithm

Kruskal's algorithm finds the Minimum Spanning Tree using Union-Find:

$1.$ Sort all edges by weight

$2.$ For each edge in order, if it connects two different components, add it to MST

$3.$ Stop when MST has $n-1$ 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: $O(E \log E)$ for sorting, plus $O(E \cdot \alpha(V)) \approx O(E)$ for union-find operations.

The cycle check (were they already connected?) is exactly what Union-Find provides efficiently.