Redundant Connection

Signal

"A tree plus one extra edge creates exactly one cycle — find the edge that causes it" is a direct union-find application: the redundant edge is the first one whose two endpoints are already connected before you'd add it.

Approach

Process edges in input order with a DSU. For each edge, check whether its two endpoints are already in the same set. If they are, this edge closes a cycle — it's the answer, and since we process in input order, the first such edge we find is also the last one that could be removed among any ties (because everything before it was still a valid, cycle-free tree). Otherwise, union the two endpoints and continue.

Skeleton

parent[i] = i for all i
def find(x): path-compress while walking up to the root
for (u, v) in edges:
    if find(u) == find(v): return [u, v]
    union(u, v)

Solution

def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    n = len(edges)
    parent = list(range(n + 1))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return [u, v]
        parent[ru] = rv

    return []

Complexity

O(n · α(n)) time — one union-find operation per edge, effectively constant each with path compression. O(n) space for the parent array.

Pitfalls

• Returning the first cycle-closing edge you find IS correct here, but only because you process edges in the given input order — sorting or reordering edges first would break the "return the one that appears last" requirement.
• Forgetting path compression turns this into a much slower solution on adversarial inputs (a long chain unioned in the worst order) — always compress on find.
• This looks like it needs a full cycle-detection DFS, but that's overkill — the incremental "would this union create a cycle" check via DSU is strictly simpler and answers exactly what's asked.