Redundant Connection

MediumGraphUnion FindDFSCycle Detection
Category: Graphs
Companies that ask this question:
AmazonGoogleFacebookMicrosoftBloomberg

Approach

Redundant Connection

Problem Statement

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 of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

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.

Example

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

Output: [2,3]

Explanation:

  • The graph initially has edges: [1,2], [1,3]
  • When we process [2,3], nodes 2 and 3 are already connected through node 1
  • Therefore [2,3] creates a cycle and is the redundant connection

Approach 1: Union-Find (Disjoint Set Union)

Algorithm

  1. Initialize Union-Find:

    • Create parent array where each node is its own parent
    • Create rank array for union by rank optimization

  2. Process Edges Sequentially:

    • For each edge [u, v]:
      • Find root of u using Find operation
      • Find root of v using Find operation
      • If roots are the same: redundant edge found (creates cycle)
      • Otherwise: Union the two components

  3. Path Compression: When finding root, compress the path by making all nodes point directly to root

  4. Union by Rank: When unioning, attach smaller tree under larger tree to keep tree height minimal

Time Complexity

  • O(E × α(N)) where α is the inverse Ackermann function (nearly constant)
  • With path compression and union by rank, operations are nearly O(1)

Space Complexity

  • O(N) for parent and rank arrays

Approach 2: Depth-First Search (DFS)

Algorithm

  1. Build Graph Incrementally: Add edges one by one
  2. Cycle Detection: Before adding each edge [u, v]:
    • Use DFS to check if u and v are already connected
    • If connected: this edge creates a cycle (redundant)
    • If not connected: add the edge and continue
  3. Return: The first edge that creates a cycle

Time Complexity

  • O(N × E) - For each edge, we potentially do DFS through entire graph
  • Less efficient than Union-Find

Space Complexity

  • O(N + E) for adjacency list and DFS stack

Key Insights

  1. Sequential Processing: Since we want the last occurring redundant edge, we process edges in order

  2. Union-Find Advantage: Perfect for dynamic connectivity queries - efficiently tracks which nodes belong to same component

  3. Path Compression: Drastically improves Find operation by flattening tree structure

  4. Union by Rank: Keeps trees balanced, preventing degeneration into linked lists

  5. Cycle Detection: An edge is redundant if and only if it connects two nodes already in the same component

Union-Find Operations

Find(x):

if parent[x] != x:
    parent[x] = find(parent[x])  // Path compression
return parent[x]

Union(x, y):

rootX = find(x)
rootY = find(y)

if rootX == rootY:
    return false  // Already connected - cycle!

// Union by rank
if rank[rootX] > rank[rootY]:
    parent[rootY] = rootX
else if rank[rootX] < rank[rootY]:
    parent[rootX] = rootY
else:
    parent[rootY] = rootX
    rank[rootX]++

return true  // Successfully united

Common Patterns

  • Union-Find: For dynamic connectivity and cycle detection
  • Graph Traversal: Alternative approach using DFS/BFS
  • Incremental Graph Building: Process edges sequentially

Related Problems

  • Graph Valid Tree
  • Number of Connected Components
  • Accounts Merge
  • Longest Consecutive Sequence

Solution

java
1class Solution {
2    // Approach 1: Union-Find Solution
3    public int[] findRedundantConnection(int[][] edges) {
4        int n = edges.length;
5        int[] parent = new int[n + 1];
6        int[] rank = new int[n + 1];
7
8        // Initialize: each node is its own parent
9        for (int i = 1; i <= n; i++) {
10            parent[i] = i;
11            rank[i] = 0;
12        }
13
14        for (int[] edge : edges) {
15            int u = edge[0];
16            int v = edge[1];
17
18            int rootU = find(u, parent);
19            int rootV = find(v, parent);
20
21            // If same root, this edge creates a cycle
22            if (rootU == rootV) {
23                return edge;
24            }
25
26            // Union the two components
27            union(rootU, rootV, parent, rank);
28        }
29
30        return new int[]{};
31    }
32
33    private int find(int x, int[] parent) {
34        if (parent[x] != x) {
35            parent[x] = find(parent[x], parent); // Path compression
36        }
37        return parent[x];
38    }
39
40    private void union(int x, int y, int[] parent, int[] rank) {
41        // Union by rank
42        if (rank[x] > rank[y]) {
43            parent[y] = x;
44        } else if (rank[x] < rank[y]) {
45            parent[x] = y;
46        } else {
47            parent[y] = x;
48            rank[x]++;
49        }
50    }
51
52    // Approach 2: DFS Solution
53    public int[] findRedundantConnectionDFS(int[][] edges) {
54        int n = edges.length;
55        List<List<Integer>> graph = new ArrayList<>();
56
57        for (int i = 0; i <= n; i++) {
58            graph.add(new ArrayList<>());
59        }
60
61        for (int[] edge : edges) {
62            int u = edge[0];
63            int v = edge[1];
64
65            // Check if u and v are already connected
66            Set<Integer> visited = new HashSet<>();
67            if (hasPath(u, v, graph, visited)) {
68                return edge; // This edge creates a cycle
69            }
70
71            // Add edge to graph
72            graph.get(u).add(v);
73            graph.get(v).add(u);
74        }
75
76        return new int[]{};
77    }
78
79    private boolean hasPath(int start, int target, List<List<Integer>> graph, Set<Integer> visited) {
80        if (start == target) return true;
81        visited.add(start);
82
83        for (int neighbor : graph.get(start)) {
84            if (!visited.contains(neighbor)) {
85                if (hasPath(neighbor, target, graph, visited)) {
86                    return true;
87                }
88            }
89        }
90
91        return false;
92    }
93
94    // Approach 3: Union-Find with Simple Path Compression
95    public int[] findRedundantConnectionSimple(int[][] edges) {
96        int[] parent = new int[edges.length + 1];
97
98        for (int i = 1; i < parent.length; i++) {
99            parent[i] = i;
100        }
101
102        for (int[] edge : edges) {
103            int x = edge[0];
104            int y = edge[1];
105
106            // Find roots
107            while (parent[x] != x) x = parent[x];
108            while (parent[y] != y) y = parent[y];
109
110            if (x == y) {
111                return edge; // Cycle detected
112            }
113
114            parent[x] = y; // Union
115        }
116
117        return new int[]{};
118    }
119}
120
Loading visualizer...