Redundant Connection

Description

In this problem, a tree is defined as an undirected graph that is connected (every node can reach every other node) and has no cycles (there is exactly one path between any two nodes).

You are given a graph that started as a tree with n nodes labeled from 1 to n, but one additional edge has been added. This extra edge connects two different nodes that were not directly connected before, creating exactly one cycle in the graph.

The graph is represented as an array edges of length n, where edges[i] = [a_i, b_i] indicates an undirected edge between nodes a_i and b_i.

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

Undirected graph with 5 nodes showing a cycle 1-2-3-4-1 and a non-cycle edge 1-5. Edge [1,4] is dashed to indicate it is redundant.

Examples

Example 1

Input: edges = [[1,2], [1,3], [2,3]]

Output: [2,3]

Explanation: The graph has 3 nodes forming a triangle: 1—2, 1—3, and 2—3. The original tree could have been 1—2 and 1—3 (a star centered at 1). The extra edge [2,3] completes the cycle 1→2→3→1. Removing [2,3] restores the tree. Note that [1,3] could also be removed, but [2,3] appears later in the input, so we return [2,3].

Example 2

Input: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]

Output: [1,4]

Explanation: The graph has 5 nodes. Edges [1,2], [2,3], [3,4] form a chain 1—2—3—4. Edge [1,4] creates the cycle 1→2→3→4→1. Edge [1,5] connects node 5 (not part of the cycle). Removing [1,4] breaks the cycle, and the remaining 4 edges form a valid tree. Edges [1,2], [2,3], or [3,4] could also break the cycle, but [1,4] appears last among the cycle edges.

Constraints

n == edges.length
3 ≤ n ≤ 1000
edges[i].length == 2
1 ≤ a_i < b_i ≤ edges.length
a_i ≠ b_i
There are no repeated edges
The given graph is connected

Editorial

Brute Force (DFS Cycle Detection)

Intuition

The key observation is: an edge is redundant if and only if the two nodes it connects are already reachable from each other through other edges. If nodes u and v are already connected, adding the edge [u, v] creates a second path between them — and that second path, combined with the existing one, forms a cycle.

So the strategy is straightforward: build the graph one edge at a time. Before adding each edge [u, v], check whether u can already reach v using the edges added so far. If yes, this edge is the one that would create the cycle — return it.

To check reachability, we run a DFS (depth-first search) from u and see if we can visit v. If the DFS reaches v, the nodes are already connected and this edge is redundant.

Step-by-Step Explanation

Let's trace with edges = [[1,2], [2,3], [3,4], [1,4], [1,5]].

Step 1: Process edge [1,2]. Graph is empty — no edges exist yet. DFS from node 1 finds no path to node 2. Not connected. Add edge [1,2] to the graph.

Step 2: Process edge [2,3]. DFS from node 2: visit 2, follow edge to 1. Dead end — node 3 not reached. Not connected. Add edge [2,3].

Step 3: Process edge [3,4]. DFS from node 3: visit 3→2→1. Node 4 not reached. Not connected. Add edge [3,4].

Step 4: Process edge [1,4]. DFS from node 1: visit 1→2→3→4. NODE 4 FOUND! Nodes 1 and 4 are already connected via path 1—2—3—4. Adding [1,4] would create cycle 1→2→3→4→1.

Step 5: Return [1,4] as the redundant edge. Edge [1,5] is never processed — we found the answer.

DFS Cycle Detection — Building Graph Edge by Edge — Watch as we add edges one at a time, running DFS before each addition to check if the endpoints are already connected. The fourth edge triggers a cycle.

Algorithm

Initialize an empty adjacency list for the graph.
For each edge [u, v] in the input:
a. Run DFS from u on the current graph to check if v is reachable.
b. If v is reachable, return [u, v] — this edge creates a cycle.
c. If v is not reachable, add [u, v] to the graph (both directions, since it's undirected).
Return the first cycle-creating edge found (which is guaranteed to be the last one in the input among the cycle's edges, due to processing order).

Code

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<vector<int>> graph(n + 1);

        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            if (isConnected(graph, u, v, n)) {
                return edge;
            }
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        return {};
    }

private:
    bool isConnected(vector<vector<int>>& graph, int src, int dst, int n) {
        vector<bool> visited(n + 1, false);
        stack<int> stk;
        stk.push(src);

        while (!stk.empty()) {
            int node = stk.top();
            stk.pop();
            if (node == dst) return true;
            if (visited[node]) continue;
            visited[node] = true;
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    stk.push(neighbor);
                }
            }
        }

        return false;
    }
};

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

        graph = defaultdict(list)

        def is_connected(source, target):
            visited = set()
            stack = [source]
            while stack:
                node = stack.pop()
                if node == target:
                    return True
                if node in visited:
                    continue
                visited.add(node)
                for neighbor in graph[node]:
                    if neighbor not in visited:
                        stack.append(neighbor)
            return False

        for u, v in edges:
            if is_connected(u, v):
                return [u, v]
            graph[u].append(v)
            graph[v].append(u)

        return []

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            if (isConnected(graph, u, v, n)) {
                return edge;
            }
            graph.get(u).add(v);
            graph.get(v).add(u);
        }

        return new int[]{};
    }

    private boolean isConnected(List<List<Integer>> graph, int src, int dst, int n) {
        boolean[] visited = new boolean[n + 1];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(src);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (node == dst) return true;
            if (visited[node]) continue;
            visited[node] = true;
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    stack.push(neighbor);
                }
            }
        }

        return false;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n edges, we run a DFS that visits up to n nodes. The DFS for the k-th edge explores a graph with at most k-1 edges and k nodes, taking O(k) time. Total: O(1 + 2 + ... + n) = O(n²). For n = 1000, this is about 500,000 operations — fast enough.

Space Complexity: O(n)

The adjacency list stores at most 2n entries (each edge appears in two lists). The DFS uses a visited array of size n and a stack of depth at most n. Total: O(n).

Why This Approach Is Not Efficient

The DFS approach works, but it does redundant work. Each time we add a new edge, we re-explore the entire graph from scratch to answer one simple question: "are these two nodes in the same component?"

For example, after adding [1,2], [2,3], [3,4], we know nodes 1-4 are all connected. But when checking edge [1,4], we run DFS from node 1 traversing through 2, 3, all the way to 4 — retracing the same connections we've already established.

What if we had a data structure that could:

Answer "are nodes u and v in the same component?" in nearly constant time?
Merge two components in nearly constant time when adding an edge?

This is exactly what Union-Find (also called Disjoint Set Union) provides. Instead of O(n) per connectivity check, Union-Find answers in O(α(n)) ≈ O(1) amortized time, reducing the total from O(n²) to essentially O(n).

Optimal Approach - Union-Find

Intuition

Union-Find maintains a forest where each tree represents a connected component. Every node has a parent pointer. The root of a tree is the representative of that component — two nodes are in the same component if and only if they share the same root.

Three operations power Union-Find:

Initialize: Each node starts as its own parent (its own component).
Find(x): Follow parent pointers from x upward until reaching the root. With path compression, we flatten the chain so every node along the way points directly to the root — making future finds almost instant.
Union(x, y): Find the roots of x and y. If they're different, make one root the parent of the other, merging the two components.

To solve our problem: process edges in order. For each edge [u, v], call find(u) and find(v). If they have the same root, they're already in the same component — this edge is redundant (it creates a cycle). If they have different roots, union them.

Because we process edges in order, the first edge whose endpoints share a root is the last cycle-creating edge in the input — exactly what the problem asks for.

Step-by-Step Explanation

Let's trace Union-Find on edges = [[1,2], [2,3], [3,4], [1,4], [1,5]].

Step 1: Initialize parent = [_, 1, 2, 3, 4, 5]. Each node is its own root.

Step 2: Process [1,2]. find(1) = 1, find(2) = 2. Different roots → no cycle. Union: parent[1] = 2. Parent array: [_, 2, 2, 3, 4, 5].

Step 3: Process [2,3]. find(2) = 2, find(3) = 3. Different roots → no cycle. Union: parent[2] = 3. Parent array: [_, 2, 3, 3, 4, 5]. Now the chain is 1→2→3.

Step 4: Process [3,4]. find(3) = 3, find(4) = 4. Different roots → no cycle. Union: parent[3] = 4. Parent array: [_, 2, 3, 4, 4, 5]. Chain: 1→2→3→4.

Step 5: Process [1,4]. find(1): follow chain 1→2→3→4. Root is 4. find(4) = 4. SAME ROOT! Nodes 1 and 4 are already connected. Cycle detected!

Step 6: Path compression updates: parent[1]=4, parent[2]=4, parent[3]=4. Return [1,4].

Union-Find — Detecting the Redundant Edge — Watch how Union-Find efficiently tracks connected components. Each union merges components, and when find() reveals two nodes already share a root, we've found the cycle-creating edge.

Algorithm

Create a parent array of size n+1, where parent[i] = i (each node is its own root).
Define find(x): recursively follow parent pointers to the root. Apply path compression — set each node's parent directly to the root during traversal.
For each edge [u, v] in the input:
a. Compute root_u = find(u) and root_v = find(v).
b. If root_u == root_v, return [u, v] — this edge creates a cycle.
c. Otherwise, union: set parent[root_u] = root_v (merge the two components).
The first cycle-creating edge found is guaranteed to be the answer.

Code

class Solution {
    vector<int> parent;

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

public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        parent.resize(n + 1);
        for (int i = 0; i <= n; i++) parent[i] = i;

        for (auto& edge : edges) {
            int pu = find(edge[0]), pv = find(edge[1]);
            if (pu == pv) return edge; // cycle detected
            parent[pu] = pv;           // union
        }

        return {};
    }
};

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

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

        for u, v in edges:
            pu, pv = find(u), find(v)
            if pu == pv:
                return [u, v]  # cycle detected
            parent[pu] = pv    # union

        return []

class Solution {
    int[] parent;

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

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

        for (int[] edge : edges) {
            int pu = find(edge[0]), pv = find(edge[1]);
            if (pu == pv) return edge; // cycle detected
            parent[pu] = pv;           // union
        }

        return new int[]{};
    }
}

Complexity Analysis

Time Complexity: O(n × α(n)) ≈ O(n)

We process n edges. For each edge, we perform two find operations and at most one union. With path compression, each find takes O(α(n)) amortized time, where α is the inverse Ackermann function. For all practical purposes, α(n) ≤ 4 for any n up to 2^(2^(2^65536)) — effectively constant. Total: n edges × O(α(n)) per edge = O(n × α(n)) ≈ O(n).

Space Complexity: O(n)

The parent array stores n+1 entries (one per node). The recursion stack for find with path compression uses at most O(log n) depth before compression, and effectively O(1) after compression. Total: O(n).

Compared to the DFS approach:

Time: O(n) vs O(n²) — a significant improvement for large inputs.
Space: O(n) vs O(n) — identical.
The improvement comes from replacing repeated graph traversals with a compact, incrementally updated data structure.

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Redundant Connection

Description

Examples

Example 1

Example 2

Constraints

Editorial

Brute Force (DFS Cycle Detection)

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Union-Find

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis