Problem Description

You are given an undirected graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The input is a list of edges, where each edge is a pair [u, v] representing an undirected connection between nodes u and v.

The added edge introduces a cycle in the tree. Your task is to find the edge that, if removed, will restore the tree structure (i.e., the graph becomes acyclic and connected). If there are multiple candidates, return the edge that occurs last in the input edges list.

• There is exactly one solution.
• Do not reuse elements or remove more than one edge.
• Input is guaranteed to form a single cycle due to the extra edge.

Thought Process

At first glance, we might consider brute-forcing the solution by removing each edge one at a time and checking if the resulting graph is a tree (i.e., connected and acyclic). However, this is inefficient, especially for large graphs.

Instead, we should recognize that the problem is about detecting a cycle in a graph. Since the graph was a tree (which is acyclic) before one extra edge was added, the cycle must involve the new edge. Thus, the problem reduces to finding the first edge that, when added, creates a cycle. This is a classic use case for the Union-Find (Disjoint Set Union) data structure, which efficiently tracks connected components and can quickly determine if adding an edge would form a cycle.

Solution Approach

We will use the Union-Find (Disjoint Set Union) data structure to solve this problem efficiently. Here’s the step-by-step approach:

1. Initialize Union-Find:
   • Create a parent array where each node is its own parent initially.
2. Process Each Edge:
   • For each edge [u, v] in edges:
   • Check if u and v are already connected (i.e., have the same root parent).
   • If they are connected, adding this edge would create a cycle. This is the redundant connection to return.
   • If they are not connected, union their sets (merge their components).
3. Return the Redundant Edge:
   • Return the first edge that forms a cycle as per the above step. Since we process edges in order, if multiple answers exist, the last one in the input will be returned.

Why Union-Find? Because it allows us to efficiently determine whether two nodes are already connected (cycle detection) in nearly constant time using path compression and union by rank optimizations.

Example Walkthrough

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

1. Edge [1,2]: 1 and 2 are not connected. Union them.
   Parent: [1, 1, 3]
2. Edge [1,3]: 1 and 3 are not connected. Union them.
   Parent: [1, 1, 1]
3. Edge [2,3]: 2 and 3 are already connected (both have parent 1). Adding this edge would create a cycle.
   Return [2,3] as the redundant connection.

The process checks each edge, and as soon as it finds that two nodes are already connected, it identifies the redundant edge.

Code Implementation

class Solution:
    def findRedundantConnection(self, edges):
        parent = [i for i in range(len(edges) + 1)]
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            px, py = find(x), find(y)
            if px == py:
                return False
            parent[px] = py
            return True
        
        for u, v in edges:
            if not union(u, v):
                return [u, v]
      

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parent(n + 1);
        for (int i = 0; i <= n; ++i) parent[i] = i;
        
        function<int(int)> find = [&](int x) {
            if (parent[x] != x)
                parent[x] = find(parent[x]);
            return parent[x];
        };
        
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            int pu = find(u), pv = find(v);
            if (pu == pv) return edge;
            parent[pu] = pv;
        }
        return {};
    }
};
      

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;
        
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            int pu = find(parent, u), pv = find(parent, v);
            if (pu == pv) return edge;
            parent[pu] = pv;
        }
        return new int[0];
    }
    
    private int find(int[] parent, int x) {
        if (parent[x] != x)
            parent[x] = find(parent, parent[x]);
        return parent[x];
    }
}
      

var findRedundantConnection = function(edges) {
    let n = edges.length;
    let parent = Array(n + 1).fill(0).map((_, i) => i);
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    for (let [u, v] of edges) {
        let pu = find(u), pv = find(v);
        if (pu === pv) return [u, v];
        parent[pu] = pv;
    }
};
      

Time and Space Complexity

• Brute-force Approach:
  • Time Complexity: O(n^2), since for each edge you might need to perform a BFS/DFS to check connectivity and cycles.
  • Space Complexity: O(n) for storing the graph and visited nodes.
• Optimized (Union-Find) Approach:
  • Time Complexity: O(n \cdot \alpha(n)), where \alpha(n) is the inverse Ackermann function, which is nearly constant for practical values of n. This is due to path compression and union by rank optimizations.
  • Space Complexity: O(n) for the parent array.

Summary

The Redundant Connection problem is a classic application of cycle detection in graphs. By recognizing that the problem reduces to finding the edge that creates a cycle in an almost-tree, we can efficiently solve it using the Union-Find data structure. This approach avoids expensive graph traversals and leverages efficient set operations to detect cycles as edges are added. The solution is both elegant and highly efficient, making it a great example of how foundational data structures can simplify complex problems.