Cycle Detection with Union-Find

Process edges one by one. An edge creates a cycle if both endpoints are already in the same component:

function findRedundantConnection(edges):
    n = edges.length
    uf = new UnionFind(n + 1) // nodes are 1-indexed

    for each (u, v) in edges:
        if not uf.union(u, v):
            return [u, v] // already connected = cycle

    return []

The insight: in a tree, every edge connects two previously disconnected nodes. The edge that connects two nodes in the same component is the extra edge.

Since the graph is a tree plus one extra edge, exactly one edge will fail the union. That edge is the redundant one.

Time: $O(n \cdot \alpha(n)) \approx O(n)$. Space: $O(n)$.