89.Redundant Connection

MediumGraphs · 10/19

Problem

A tree with n nodes labelled 1 to n had one extra edge added, creating a graph with n edges. The extra edge connects two different nodes and is not a duplicate of an existing edge. The graph is given as edges, where edges[i] = [a, b] is an undirected edge.

Return an edge that can be removed so the remaining graph is a tree of n nodes. If there are multiple answers, return the one that appears last in edges.

Examples

Input:  edges = [[1,2],[1,3],[2,3]]
Output: [2,3]
Explanation: 1-2-3-1 is a triangle. Any of its three edges could go; [2,3] is the last one listed.

Input:  edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
Output: [1,4]
Explanation: The cycle is 1-2-3-4-1. Of its edges, [1,4] appears last in the input. [1,5] is not on the cycle.

Constraints

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= a < b <= n
No repeated edges; the given graph is connected

💡 Key Insight

A tree plus one edge contains exactly one cycle, and the answer is the last-listed edge on it. Process edges in input order while tracking which nodes are already connected: the first edge whose two endpoints are already in the same component closes the cycle. Every cycle edge was added earlier, so this edge is precisely the last cycle edge in the input. Union-Find answers "same component?" and merges components in near-O(1) time.

Brute Force (DFS Before Each Edge)

TimeO(n²)SpaceO(n)

Intuition

Build the graph one edge at a time. Before adding [u, v], run a DFS from u over the edges added so far. If v is already reachable, the new edge would create a cycle — return it. Because edges are processed in order, the first such edge is the last cycle edge in the input.

Algorithm

Start with an empty adjacency list for nodes 1..n.
For each edge [u, v]:
- If dfs(u, v) (with a fresh visited array) reaches v, return [u, v].
- Otherwise add v to graph[u] and u to graph[v].
Return an empty array (unreachable for valid input).

Visualization

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

[1,2]: can 1 reach 2? no  → add
[2,3]: can 2 reach 3? no  → add
[3,4]: can 3 reach 4? no  → add
[1,4]: can 1 reach 4? 1 → 2 → 3 → 4  yes → return [1,4]

Code

java

import java.util.ArrayList;
import java.util.List;

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[] e : edges) {
            int u = e[0], v = e[1];
            // If u can already reach v, this edge closes a cycle
            if (reachable(graph, u, v, new boolean[n + 1])) return e;
            graph.get(u).add(v);
            graph.get(v).add(u);
        }
        return new int[0];
    }

    private boolean reachable(List<List<Integer>> graph, int cur, int target, boolean[] visited) {
        if (cur == target) return true;
        visited[cur] = true;
        for (int next : graph.get(cur)) {
            if (!visited[next] && reachable(graph, next, target, visited)) return true;
        }
        return false;
    }
}

Complexity

Time: O(n²) — up to n edges, each followed by a DFS over up to n nodes and edges.
Space: O(n) — adjacency lists, visited and recursion depth.

Find the Cycle with One DFS

TimeO(n)SpaceO(n)

Intuition

Build the full graph once and run a single DFS from node 1, remembering each node's DFS parent. In an undirected DFS, reaching an already-visited node that is not your parent means you found the cycle: walk parent pointers back from the current node to that node to collect every node on the cycle. Since there is only one cycle, an edge lies on it exactly when both endpoints are cycle nodes. Scan edges from the end and return the first such edge.

Algorithm

Build adjacency lists for all edges.
dfs(u, p): mark u visited, parent[u] = p. For each neighbour v != p: if v is visited, record cycleStart = v, cycleEnd = u and stop; otherwise recurse.
Mark cycleStart and every node from cycleEnd up the parent chain until cycleStart as onCycle.
Iterate edges backwards; return the first edge with both endpoints on the cycle.

Dry Run

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

dfs(1) → dfs(2) → dfs(3) → dfs(4)
at 4: neighbour 1 is visited and not the parent (3)
      cycleStart = 1, cycleEnd = 4
parent chain: 4 → 3 → 2 → 1   onCycle = {1,2,3,4}

scan backwards: [1,5] (5 not on cycle) → [1,4] both on cycle → return [1,4]

Code

java

import java.util.ArrayList;
import java.util.List;

class Solution {
    private List<List<Integer>> graph;
    private boolean[] visited;
    private int[] parent;
    private int cycleStart = -1, cycleEnd = -1;

    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        visited = new boolean[n + 1];
        parent = new int[n + 1];
        dfs(1, 0); // graph is connected, so node 1 reaches the cycle

        // Collect the nodes on the cycle by walking parent pointers
        boolean[] onCycle = new boolean[n + 1];
        onCycle[cycleStart] = true;
        for (int node = cycleEnd; node != cycleStart; node = parent[node]) {
            onCycle[node] = true;
        }

        // Last edge in input whose endpoints are both on the cycle
        for (int i = n - 1; i >= 0; i--) {
            if (onCycle[edges[i][0]] && onCycle[edges[i][1]]) return edges[i];
        }
        return new int[0];
    }

    private boolean dfs(int u, int p) {
        visited[u] = true;
        parent[u] = p;
        for (int v : graph.get(u)) {
            if (v == p) continue;     // don't walk straight back along the tree edge
            if (visited[v]) {         // back edge: v is an ancestor on the cycle
                cycleStart = v;
                cycleEnd = u;
                return true;
            }
            if (dfs(v, u)) return true;
        }
        return false;
    }
}

Complexity

Time: O(n) — one DFS over n nodes and n edges, plus a linear scan of edges.
Space: O(n) — adjacency lists, visited, parent, onCycle and recursion depth.

Union-FindOptimal

TimeO(n·α(n))SpaceO(n)

Intuition

Union-Find keeps a set per connected component. For each edge [u, v] in order: if find(u) == find(v), then u and v are already connected through earlier edges, so this edge closes the cycle — return it. Otherwise union them. Path compression plus union by rank make each operation effectively constant time, and we never need adjacency lists or a second pass.

Algorithm

parent[i] = i, rank[i] = 0 for 1..n.
For each edge [u, v]:
- If find(u) == find(v), return [u, v].
- Otherwise attach the lower-rank root under the higher-rank root.
Return an empty array (unreachable for valid input).

Dry Run

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

flowchart TD
    S["sets: {1} {2} {3} {4} {5}"] -->|"[1,2]: roots differ"| A["{1,2} {3} {4} {5}"]
    A -->|"[2,3]: roots differ"| B["{1,2,3} {4} {5}"]
    B -->|"[3,4]: roots differ"| C["{1,2,3,4} {5}"]
    C -->|"[1,4]"| D{"find(1) == find(4)?"}
    D -->|"yes: same set"| R["return [1,4]"]

Code

java

class Solution {
    private int[] parent;
    private int[] rank;

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

        for (int[] e : edges) {
            if (!union(e[0], e[1])) {
                return e; // endpoints already connected: this edge closes the cycle
            }
        }
        return new int[0];
    }

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

    // Returns false if a and b were already in the same set
    private boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (rank[ra] < rank[rb]) {
            int tmp = ra; ra = rb; rb = tmp;
        }
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
        return true;
    }
}

Complexity

Time: O(n·α(n)) — one find/union per edge; α is the inverse Ackermann function (at most 4 for any practical n).
Space: O(n) — the parent and rank arrays.

Complexity Comparison

Approach	Time	Space
Brute Force (DFS Before Each Edge)	O(n²)	O(n)
Find the Cycle with One DFS	O(n)	O(n)
Union-Find	O(n·α(n))	O(n)

Common Pitfalls

Sizing arrays as n instead of n + 1 — nodes are labelled 1..n, not 0..n-1.
Returning the first cycle edge found by a cycle-only DFS instead of the one that appears last in edges.
Comparing parent[u] == parent[v] instead of find(u) == find(v); only roots identify a set.
In the undirected DFS, treating the edge back to the immediate parent as a cycle.
Building the full graph before running the incremental check — the brute force must only see edges added before the current one.