Redundant Connection

Some graph questions arrive one edge at a time: "add this cable — was it needed?" "Merge these two accounts." Re-running a traversal after every edge is far too slow. Union-Find answers "are these two already in the same group?" and "merge these two groups" in almost constant time each, and this problem is its classic showcase.

The problem

A network started as a tree of n nodes, numbered 1 to n: connected, with no cycles. Then one extra edge was added between two different nodes, which created exactly one cycle. You are given the n edges in order. Return an edge you can remove to get a tree back. If several edges would work, return the one that comes last in the list.

Example 1. edges = [[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]] → [1, 4]. The cycle is 1–2–3–4–1. Any of its four edges could go; [1, 4] is the last of them in the list.

Example 2. edges = [[1, 2], [1, 3], [2, 3]] → [2, 3]. The triangle's last edge.

Constraints. 3 to 10^5 nodes.

Clarifying questions

• Undirected edges? Yes. (The directed version is a harder variant.)
• Exactly one extra edge? Yes, so exactly one cycle exists.
• Nodes 1 to n, with no gaps? Yes.
• Return format? The edge as it appears in the input, [u, v].

Approach 1: the simple way

Add the edges one at a time. Before adding [u, v], check with a DFS whether u can already reach v. If it can, this edge closes a cycle — it is the answer. Otherwise add it.

1from collections import defaultdict234def redundant_brute(edges: list[list[int]]) -> list[int]:5    """Before adding each edge, DFS to see if its ends are already connected."""6    graph: dict[int, list[int]] = defaultdict(list)78    def connected(a: int, b: int) -> bool:9        seen, stack = {a}, [a]10        while stack:11            node = stack.pop()12            if node == b:13                return True14            for nxt in graph[node]:15                if nxt not in seen:16                    seen.add(nxt)17                    stack.append(nxt)18        return False1920    for u, v in edges:21        if connected(u, v):22            return [u, v]23        graph[u].append(v)24        graph[v].append(u)25    return []

Why is the first cycle-closing edge the one to return? The cycle forms only when its last edge arrives. That edge is the latest cycle edge in the list, which is exactly what the problem asks for.

The cost: each check is a DFS over the graph built so far, up to O(n). With n edges, that is O(n²). For 10^5 nodes, about 10^10 steps in the worst case — for instance when the edges build one long chain and every check walks most of it.

The key insight

The DFS answers a far richer question than we asked. We never need a path between u and v; we only need to know whether they are in the same group. And groups only ever merge — an edge never splits them.

That is exactly what Union-Find is for. Each group is stored as a small tree of parent pointers, and the root is the group's name. find(x) climbs to the root. union(a, b) joins the two roots. Two nodes are connected exactly when find gives the same root. An edge whose ends already share a root is the redundant one.

Approach 2: Union-Find

1class UnionFind:2    """Disjoint sets with path halving and union by rank."""34    def __init__(self, n: int) -> None:5        self.parent = list(range(n))6        self.rank = [0] * n7        self.count = n                           # number of separate groups89    def find(self, x: int) -> int:10        while self.parent[x] != x:11            self.parent[x] = self.parent[self.parent[x]]   # skip a level12            x = self.parent[x]13        return x1415    def union(self, a: int, b: int) -> bool:16        """Merge the groups of a and b. False if they were already one group."""17        ra, rb = self.find(a), self.find(b)18        if ra == rb:19            return False20        if self.rank[ra] < self.rank[rb]:21            ra, rb = rb, ra                      # ra is now the taller tree22        self.parent[rb] = ra23        if self.rank[ra] == self.rank[rb]:24            self.rank[ra] += 125        self.count -= 126        return True272829def find_redundant_connection(edges: list[list[int]]) -> list[int]:30    """The first edge whose ends are already in one group closes the cycle."""31    uf = UnionFind(len(edges) + 1)               # nodes are numbered 1..n32    for u, v in edges:33        if not uf.union(u, v):34            return [u, v]35    return []

Step by step:

1. Every node starts as its own group: parent[x] = x.
2. For each edge, union(u, v) finds both roots. Different roots: join them and return True. Same root: return False — this edge is redundant.
3. Union by rank hangs the shorter tree under the taller one, so trees stay shallow. rank is an upper bound on a tree's height.
4. Path compression — here the "path halving" form — makes each node on the way to the root point to its grandparent. Every find flattens the tree a little for the next one.

Why both? Without them, the unions 1–2, 2–3, 3–4, … can build a chain n long, and each find walks all of it: back to O(n) per operation. Union by rank alone limits the height to O(log n). Together with path compression, the cost per operation is O(α(n)): effectively constant.

Dry run on Example 1. Index 0 is unused.

The answer is [1, 4]. Edge [1, 5] is never examined.

Complexity. Time O(n × α(n)), effectively O(n). Space O(n) for the two arrays. On 10^5 edges, a few hundred thousand steps instead of 10^10.

Edge cases

• The extra edge is the last one in the list (Example 2) → found on the last iteration.
• The cycle is the whole graph → each node has two edges; the last cycle edge is still the first that finds equal roots.
• Nodes numbered from 1 → size the arrays n + 1 and ignore index 0, or subtract 1 from every label. Mixing the two is a classic off-by-one.
• Edges given as [v, u] instead of [u, v] → union is symmetric; return the edge exactly as given.

Follow-ups

• "Count the connected components." Union every edge, then read uf.count, which drops by 1 on each successful union. A DFS with an outer loop works too; Union-Find wins when edges keep arriving.
• "Merge accounts that share any email address." Union-Find over emails: union each account's emails with its first one, then group emails by root.
• "The edges are directed, and the graph was a rooted tree." The harder variant: a node may now have two parents. Check for that first, then fall back to cycle detection with Union-Find.