Redundant Connection

Problem Description

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges where edges[i] = [ai, bi] indicates there is an edge between nodes ai and bi.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Examples

Constraints

• n == edges.length
• 3 ≤ n ≤ 1000
• edges[i].length == 2
• 1 ≤ ai < bi ≤ edges.length
• ai != bi
• There are no repeated edges

Union-Find: Detect the Cycle-Creating Edge

Process edges one by one. For each edge (u, v), try to union u and v. If they’re already in the same set, this edge creates a cycle. Return it immediately. The problem guarantees exactly one such edge exists, and since we return on first detection, we automatically return the last such edge in input order.

Use path compression and union by rank for near-O(1) operations per edge.

Solution: Union-Find

class Solution {
    private int[] parent, rank;

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        parent = new int[n + 1];
        rank = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;

        for (int[] edge : edges) {
            if (!union(edge[0], edge[1])) {
                return edge; // cycle detected
            }
        }
        return new int[]{};
    }

    private int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
        return parent[x];
    }

    private boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false; // already connected: cycle!
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else { parent[py] = px; rank[px]++; }
        return true;
    }
}

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

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

        def union(x: int, y: int) -> bool:
            px, py = find(x), find(y)
            if px == py:
                return False  # cycle!
            if rank[px] < rank[py]:
                parent[px] = py
            elif rank[px] > rank[py]:
                parent[py] = px
            else:
                parent[py] = px
                rank[px] += 1
            return True

        for u, v in edges:
            if not union(u, v):
                return [u, v]

        return []

#include <vector>
#include <numeric>

class Solution {
    std::vector<int> parent, rank_;

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank_[px] < rank_[py]) std::swap(px, py);
        parent[py] = px;
        if (rank_[px] == rank_[py]) rank_[px]++;
        return true;
    }

public:
    std::vector<int> findRedundantConnection(std::vector<std::vector<int>>& edges) {
        int n = edges.size();
        parent.resize(n + 1); std::iota(parent.begin(), parent.end(), 0);
        rank_.assign(n + 1, 0);

        for (auto& e : edges) {
            if (!unite(e[0], e[1])) return e;
        }
        return {};
    }
};

Complexity Analysis:

• Time Complexity: O(n * alpha(n)) where alpha is the inverse Ackermann function. Effectively O(n) for all practical purposes.
• Space Complexity: O(n) for parent and rank arrays.

Where it breaks: the problem guarantees exactly one redundant edge. Without this guarantee, you’d need to track all cycle-forming edges. Path compression + union by rank is essential for large n to avoid O(n²) in degenerate cases.

Common Mistakes

• Using DFS to detect cycles. DFS works but is O(n) per edge check, giving O(n²) total. Union-Find is asymptotically faster.
• Not using path compression. Without it, find() degrades to O(n) per call on a chain graph.

← All Problems