Redundant Connection

How it works

Use Disjoint Set Union (Union-Find) to track connected components while adding edges one by one.

• Initially, every node is its own component.
• When we add an edge (u, v):
  • If u and v are already in the same component, adding this edge creates a cycle.
  • That edge is exactly the redundant connection.
• If they are in different components, we safely merge them.

Because edges are processed in order, the first edge that fails to union is the answer.

Steps

1. Initialize DSU where each node is its own parent.
2. For each edge (u, v):
   • Find the parent of u and v.
   • If both parents are the same:
     • Return (u, v) → this edge creates a cycle.
   • Otherwise, union the two components.
3. The first edge that cannot be unioned is the redundant edge.

This works because a tree with n nodes has exactly n - 1 edges, and any extra edge must form a cycle.

Complexity

• Time complexity: O(V + (E * α(V)))
• Space complexity: O(V)

Where V is the number of vertices and E is the number of edges in the graph. α() is used for amortized complexity.

Things to watch for

Returning the First Cycle Edge Instead of the Last

The problem asks for the edge that appears last in the input among all edges that could be removed to break the cycle. A common mistake is returning the first edge that creates a cycle during processing. When using Union-Find, processing edges in order naturally returns the correct answer, but DFS-based approaches must scan edges in reverse to find the last valid edge.

Treating the Graph as Directed

This problem involves an undirected graph, but some solutions incorrectly handle edges as directed. When building the adjacency list, each edge (u, v) must be added in both directions. Forgetting this causes cycle detection to miss valid paths and return incorrect results.

Not Handling the Parent Node in DFS Cycle Detection

When using DFS to detect cycles in an undirected graph, you must skip the parent node to avoid false positives. In an undirected graph, the edge (u, v) appears as both u -> v and v -> u in the adjacency list. Without parent tracking, DFS would immediately detect a "cycle" by going back to the node it just came from.

from typing import List

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        par = [i for i in range(len(edges) + 1)]
        rank = [1] * (len(edges) + 1)

        def find(n):
            p = par[n]
            while p != par[p]:
                par[p] = par[par[p]]
                p = par[p]
            return p

        def union(n1, n2):
            p1, p2 = find(n1), find(n2)

            if p1 == p2:
                return False
            if rank[p1] > rank[p2]:
                par[p2] = p1
                rank[p1] += rank[p2]
            else:
                par[p1] = p2
                rank[p2] += rank[p1]
            return True

        for n1, n2 in edges:
            if not union(n1, n2):
                return [n1, n2]

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> par(n + 1), rank(n + 1, 1);
        for (int i = 0; i <= n; ++i)
            par[i] = i;

        for (const auto& edge : edges) {
            if (!Union(par, rank, edge[0], edge[1]))
                return vector<int>{ edge[0], edge[1] };
        }
        return {};
    }

private:
    int Find(vector<int>& par, int n) {
        int p = par[n];
        while (p != par[p]) {
            par[p] = par[par[p]];
            p = par[p];
        }
        return p;
    }

    bool Union(vector<int>& par, vector<int>& rank, int n1, int n2) {
        int p1 = Find(par, n1);
        int p2 = Find(par, n2);

        if (p1 == p2)
            return false;
        if (rank[p1] > rank[p2]) {
            par[p2] = p1;
            rank[p1] += rank[p2];
        } else {
            par[p1] = p2;
            rank[p2] += rank[p1];
        }
        return true;
    }
};