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.

Additional information

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ai < bi <= edges.length
• ai != bi
• There are no repeated edges.
• The given graph is connected.

Example 1:

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

Output: [2,3]

Example 2:

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

Output: [1,4]

Brute Force (Cycle Detection with DFS)

Intuition

A tree is simply a connected graph with absolutely no cycles. The problem states that exactly one extra edge was added to a valid tree, creating a single cycle.

We can build the graph edge by edge. Before we add an edge connecting node u and node v to our adjacency list, we can run a Depth-First Search (DFS) to see if a path already exists between u and v. If a path already exists, it means adding this new edge will create a loop! Because we are iterating through the input edges array in order, the very first time we detect this loop is guaranteed to be the "last occurring" redundant connection that caused the cycle.

Algorithm

1. Initialize an empty adjacency list adj using a dictionary.
2. Define a recursive helper function dfs(source, target, visited):

• If source == target, we found a path! Return True.
• Add source to the visited set.
• Iterate through all neighbors of source in adj.
• If a neighbor hasn't been visited, recursively call dfs on it. If it returns True, return True.
• Return False if no path is found.

3. Iterate through each edge [u, v] in the input edges.
4. If both u and v are already in adj, run dfs(u, v, set()).

• If dfs returns True, adding this edge creates a cycle. Return [u, v].

5. If no cycle is detected, add u to adj[v] and v to adj[u] to officially build the edge.
6. Return an empty array (though the problem guarantees a redundant edge exists).

def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    adj = defaultdict(list)
    
    def dfs(source, target, visited):
        if source == target:
            return True
            
        visited.add(source)
        
        for neighbor in adj[source]:
            if neighbor not in visited:
                if dfs(neighbor, target, visited):
                    return True
                    
        return False
        
    for u, v in edges:
        # If both nodes exist in the graph, check if a path already connects them
        if u in adj and v in adj:
            if dfs(u, v, set()):
                return [u, v]
                
        # Add the edge to the graph
        adj[u].append(v)
        adj[v].append(u)
        
    return []

Time & Space Complexity

• Time complexity: O(N^2)

• Reason: For each of the N edges, we potentially run a DFS that can visit up to N nodes. This results in quadratic time complexity.

• Space complexity: O(N)

• Reason: The adjacency list adj stores up to N edges. The recursion stack for the DFS and the visited set can also hold up to N elements.

Union-Find (Disjoint Set) - Optimal

Intuition

We can solve this incredibly fast using the Union-Find (or Disjoint Set) algorithm.

Imagine every node starting in its own isolated set. When we process an edge between u and v, we check if they are already in the same set. If they have different "roots" (parents), they are in separate sets, and we merge (Union) them.

If we find an edge where u and v already share the exact same root, it means they were already connected through previous edges. Adding this current edge creates a cycle! We immediately return it. By using "Path Compression" and "Union by Rank", we can find and merge sets in near-constant O(1) time.

Algorithm

1. Create a parent array of size N + 1 (since nodes are 1-indexed) where each node is initially its own parent.
2. Create a rank array of size N + 1 initialized to 1 (used to keep trees shallow during unions).
3. Define the find(n) function with Path Compression:

• Follow the parent pointers until you reach a node that is its own parent (the root).
• Compress the path by making nodes point directly to the root as you traverse back up.

4. Define the union(n1, n2) function:

• Find the roots of n1 and n2 (p1 and p2).
• If p1 == p2, they are already connected. Return False (cycle detected).
• Otherwise, attach the tree with the smaller rank to the root of the tree with the larger rank.
• Update the rank of the new root. Return True.

5. Iterate through edges. For each [u, v], if union(u, v) returns False, return [u, v].

def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    # Nodes are 1-indexed, so we allocate len(edges) + 1
    parent = [i for i in range(len(edges) + 1)]
    rank = [1] * (len(edges) + 1)
    
    def find(n):
        p = parent[n]
        while p != parent[p]:
            # Path compression: point directly to the grandparent
            parent[p] = parent[parent[p]]
            p = parent[p]
        return p
        
    def union(n1, n2):
        p1, p2 = find(n1), find(n2)
        
        # If they share the same root, a cycle is found
        if p1 == p2:
            return False
            
        # Union by rank: attach smaller tree under larger tree
        if rank[p1] > rank[p2]:
            parent[p2] = p1
            rank[p1] += rank[p2]
        else:
            parent[p1] = p2
            rank[p2] += rank[p1]
            
        return True
        
    for u, v in edges:
        if not union(u, v):
            return [u, v]
            
    return []

Time & Space Complexity

• Time complexity: O(N)

• Reason: Processing each of the N edges takes amortized O(1) time due to the Path Compression and Union by Rank optimizations in the Union-Find algorithm. Mathematically, it is O(N * α(N)), where α is the Inverse Ackermann function (which is effectively constant for all reasonable values of N).

• Space complexity: O(N)

• Reason: The parent and rank arrays both take exactly O(N) auxiliary space.