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)

An edge is redundant if its endpoints are already connected before you add it. Scan edges in order; before adding [a, b], run a DFS/BFS over the graph built so far to check whether b is already reachable from a. The first edge for which it is, is the answer.

def findRedundantConnection(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 repeats work; union-find does the same job in one pass.

Approach 2 — Union-Find (optimal)

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, so union them. If they are equal, both endpoints are already in the same component, so this edge closes a cycle and is redundant. Because you scan in input order, the first such edge is exactly the last cycle edge in the input. Union-find (disjoint-set union) supports near-constant find/union via path compression and union by rank.

def findRedundantConnection(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].

graph TD
    1 --- 2
    1 --- 3
    2 -.redundant.- 3

Edges [1,2] and [1,3] build the tree; [2,3] (dashed) joins two nodes already in the same component and closes the cycle.

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 standard tool for undirected cycle detection while building a graph incrementally: an edge whose endpoints already share a root would create a cycle. The same “detect the edge that closes a cycle” idea drives Kruskal’s MST, which rejects cycle-closing edges. Reach for DFS/BFS connectivity only when you are not adding edges one at a time.