Redundant Connection

Problem

Start with a tree of n nodes labeled 1 to n (a connected, acyclic, undirected graph with exactly n - 1 edges). Someone adds one extra edge, so you’re given n edges total in edges, where each edges[i] = [a, b] is undirected. The extra edge creates exactly one cycle.

Return the one edge that can be removed so the remaining graph is again a tree. If more than one answer exists, return the edge that appears last in the input.

Examples

• edges = [[1,2],[1,3],[2,3]] → [2,3] — nodes 1,2,3 form a triangle; removing [2,3] (the last edge closing the cycle) leaves a valid tree.
• edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] → [1,4] — the cycle is 1–2–3–4–1; [1,4] is the last edge that completes it.
• edges = [[1,2],[2,3],[1,3]] → [1,3] — triangle again; [1,3] is the last edge forming the cycle.

Constraints

• n == len(edges), 3 <= n <= 1000
• Nodes are labeled 1 to n; the graph is connected with exactly one cycle.
• No self-loops and no repeated edges.

Think about it first

TL;DR

Add edges one by one; the first edge joining two already-connected nodes closes the cycle — detect it with union-find — O(n·α(n)) time, O(n) space.

Approach 1 — Brute force (re-check connectivity per edge with DFS)

The insight: an edge is redundant if its endpoints are already connected before you add it. So, scanning edges in order, before adding [a, b] run a DFS/BFS in the graph built so far to see if b is already reachable from a. The first edge for which it is, is the answer.

class Solution:
    def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:
        from collections import defaultdict
        adj = defaultdict(set)

        def connected(a: int, b: int) -> bool:
            seen = {a}
            stack = [a]
            while stack:
                node = stack.pop()
                if node == b:
                    return True
                for nxt in adj[node]:
                    if nxt not in seen:
                        seen.add(nxt)
                        stack.append(nxt)
            return False

        for a, b in edges:
            if a in adj and b in adj and connected(a, b):
                return [a, b]
            adj[a].add(b)
            adj[b].add(a)
        return []

Complexity: each of n edges triggers an O(n) DFS → O(n²) time. It works for n ≤ 1000 but is wasteful; the union-find version is far cleaner and faster.

Approach 2 — Union-Find (optimal)

The insight: maintain the connected components as you add edges. For each edge, find the roots of both endpoints. If they differ, the edge links two separate trees — union them. If they’re equal, both endpoints are already in the same component, so this edge closes the cycle: it’s redundant. Scanning in input order means the first such edge found is the last one in the input among cycle edges. Union-find (disjoint-set union) supports near-O(1) find/union via path compression and union by rank.

class Solution:
    def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:
        n = len(edges)
        parent = list(range(n + 1))          # nodes are 1..n
        rank = [1] * (n + 1)

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

        def union(a: int, b: int) -> bool:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False                     # already connected -> redundant
            if rank[ra] < rank[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            rank[ra] += rank[rb]
            return True

        for a, b in edges:
            if not union(a, b):
                return [a, b]
        return []

Walkthrough (edges = [[1,2],[1,3],[2,3]]): union(1,2) merges {1,2}. union(1,3) merges {1,2,3}. For [2,3], find(2) and find(3) both return the same root → union returns False → return [2, 3].

Complexity: each find/union is effectively O(α(n)) (inverse Ackermann ≈ constant) → O(n·α(n)) time, O(n) space for the parent and rank arrays.

Common pitfalls

• Sizing arrays for 0-indexing. Nodes are labeled 1..n, so allocate n + 1 slots and ignore index 0.
• Returning on the wrong edge. The redundant edge is the one whose endpoints were already connected — not merely any edge in a triangle. Union-find pinpoints it exactly.
• Skipping path compression / union by rank. Without them find can degrade toward O(n) on adversarial chains; with them it’s near-constant.
• Assuming input order doesn’t matter. The problem specifically wants the last cycle edge; process edges left-to-right so the first detected cycle-closing edge is that one.

Pattern takeaway

Union-find is the go-to for undirected cycle detection while building a graph incrementally: an edge whose endpoints already share a root would create a cycle. This “detect the edge that closes a cycle” idea generalizes to Kruskal’s MST (reject cycle-closing edges) and any “is adding this connection redundant?” question. Reach for DFS/BFS connectivity only when you’re not adding edges one at a time.