Redundant Connection

You'll use union-find to track which nodes are already connected, so the edge that closes a cycle stands out. You need graphs and paths. Related chapter: topological sort and union-find.

1. The problem

A graph started as a tree on nodes 1 to n, and then got one extra edge. Edges have no direction. You get all n edges, with no repeats. Return an edge you can remove to get a tree back. If several work, return the one that comes last in the input. Don't change the input. Our function also returns [] for an empty list. LeetCode 684.

2. A correct baseline

Try removing each edge, starting from the last, and check whether every node is still connected. What's left has n − 1 edges, so if it's connected, it's a tree.

def baseline(edges):
    n = len(edges)
    for removed in range(n - 1, -1, -1):
        graph = [[] for _ in range(n + 1)]
        for i, (u, v) in enumerate(edges):
            if i != removed:
                graph[u].append(v)
                graph[v].append(u)
        seen, pending = {1}, [1]
        while pending:
            for v in graph[pending.pop()]:
                if v not in seen:
                    seen.add(v)
                    pending.append(v)
        if len(seen) == n:
            return edges[removed][:]
    return []

assert baseline([[1, 2], [1, 3], [2, 3]]) == [2, 3]
assert baseline([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]) == [1, 4]
assert baseline([[2, 3], [1, 3], [1, 2]]) == [1, 2]
assert baseline([]) == []

Each try rebuilds the graph and walks it, so this takes O(n²) time in the worst case. With 1,000 edges, that's about a million steps. It uses O(n) extra space.

The bottleneck. Each try rebuilds and walks almost the same graph.

3. The observation

Add the edges one at a time instead. In the first example, [1,2] joins 1 and 2, and [1,3] joins 3 to them. When [2,3] arrives, 2 and 3 are already connected through 1. So [2,3] closes a cycle, and it's the edge to remove.

To check "already connected?" quickly, use union-find. It keeps each group of connected nodes as a small tree with one root. Two nodes are connected exactly when they have the same root. Adding an edge between two groups merges them by pointing one root at the other.

Why is the first cycle-closing edge the one LeetCode wants? A tree plus one edge has exactly one cycle. When the cycle's last edge arrives, all its other edges are already in. So the edge that closes the cycle is the cycle edge that comes last in the input. Edges after it aren't on the cycle, and removing them would cut the graph apart.

4. The solution and a trace

class Solution:
    def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:
        """Simple undirected tree plus one edge, labels 1..len(edges); [] extends it."""
        parent = list(range(len(edges) + 1))
        size = [1] * len(parent)
        def find(node):
            while node != parent[node]:
                parent[node] = parent[parent[node]]  # Halve the path to its root.
                node = parent[node]
            return node
        for u, v in edges:
            a, b = find(u), find(v)
            if a == b:
                return [u, v]
            # Attach the smaller component to the larger representative.
            if size[a] < size[b]:
                a, b = b, a
            parent[b] = a
            size[a] += size[b]
        return []

solve = Solution().findRedundantConnection
assert solve([[1, 2], [1, 3], [2, 3]]) == [2, 3]
assert solve([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]]) == [1, 4]
assert solve([[2, 3], [1, 3], [1, 2]]) == [1, 2]
assert solve([]) == []

Trace the first example:

5. Why it works

What stays true. Two nodes have the same root exactly when the edges so far connect them. That's true at the start, when every node is alone. Merging two groups keeps it true.

The returned edge closes a cycle. If both ends already share a root, a path already joins them. Adding the edge makes a cycle.

It's the right edge. There's only one cycle, and this is its last edge in the input. Removing it leaves n − 1 edges that still connect every node, which is a tree. Removing an edge that isn't on the cycle would cut the graph apart, so no such edge can be the answer.

6. Cost, edge cases, and failure

Cost. Each of the n edges does two find calls. Attaching the smaller group to the larger one, and shortening paths during find, keeps every call nearly O(1) on average. The total is effectively O(n) time. (The exact bound is O(n α(n)), where α grows so slowly it's below 5 for any real input.) It uses O(n) space.

Edge cases. size is only accurate at a group's root, which is the only place it's read. The function returns a new list and doesn't change the input. The "last in the input" rule relies on LeetCode's promise of exactly one extra edge.

Where it fails. Union-find can't find cycles in a graph whose edges have a direction. Two connected nodes don't mean there's a path in the right direction:

edges = [[1, 2], [1, 3], [2, 3]]
assert solve(edges) == [2, 3]
assert all(u < v for u, v in edges)  # As arrows, 1,2,3 is a valid topological order.
# Thus treating this DSU result as a directed-cycle witness would be wrong.

import random
from itertools import combinations, permutations
rng = random.Random(684)
for _ in range(500):
    n = rng.randrange(3, 15)
    edges = [[rng.randrange(1, v), v] for v in range(2, n + 1)]
    used = {tuple(edge) for edge in edges}
    choices = [pair for pair in combinations(range(1, n + 1), 2) if pair not in used]
    edges.append(list(rng.choice(choices)))
    rng.shuffle(edges)
    before = [edge[:] for edge in edges]
    actual = solve(edges)
    assert actual == baseline(edges)
    assert edges == before and all(actual is not edge for edge in edges)
# All 360 orderings of simple four-node, four-edge graphs are connected here.
for chosen in combinations(combinations(range(1, 5), 2), 4):
    for order in permutations(chosen):
        edges = [list(edge) for edge in order]
        assert solve(edges) == baseline(edges)