Redundant Connection

medium graph union find dfs

Problem

In a graph with n nodes labeled 1..n there is exactly one extra edge that turns a tree into a graph with one cycle. Given an edge list, return the edge that should be removed so that the result is a tree. If there are multiple answers, return the last one in input order.

Inputedges = [[1,2], [1,3], [2,3]]

Output[2, 3]

When we add [2,3], 2 and 3 already share root 1 — that closes a cycle.

edges (e.g. "1-2,1-3,2-3")

def find_redundant(edges):
    parent = list(range(len(edges) + 1))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return [u, v]
        parent[ru] = rv
    return []

function findRedundantConnection(edges) {
  const parent = Array.from({length: edges.length + 1}, (_, i) => i);
  function find(x) {
    while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
  }
  for (const [u, v] of edges) {
    const ru = find(u), rv = find(v);
    if (ru === rv) return [u, v];
    parent[ru] = rv;
  }
  return [];
}

class Solution {
    int[] parent;
    public int[] findRedundantConnection(int[][] edges) {
        parent = new int[edges.length + 1];
        for (int i = 0; i < parent.length; i++) parent[i] = i;
        for (int[] e : edges) {
            int ru = find(e[0]), rv = find(e[1]);
            if (ru == rv) return e;
            parent[ru] = rv;
        }
        return new int[0];
    }
    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
}

vector<int> parent;
int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    parent.resize(edges.size() + 1);
    iota(parent.begin(), parent.end(), 0);
    for (auto& e : edges) {
        int ru = find(e[0]), rv = find(e[1]);
        if (ru == rv) return e;
        parent[ru] = rv;
    }
    return {};
}

Explanation

We have a tree with one extra edge that creates a single cycle, and we want the last edge that closes that loop. The clean way to find it is Union-Find: a structure that groups nodes into connected sets and can quickly tell whether two nodes already belong to the same group.

Each node starts as its own group, stored in parent where parent[i] = i. The helper find(x) follows parent pointers up to the root (the representative) of a node's group, flattening the path as it goes so future lookups are fast.

We add edges one at a time. For edge [u, v] we compute find(u) and find(v). If the two roots are different, the edge joins two separate groups, so we union them. If the two roots are the same, then u and v were already connected — adding this edge would make a cycle, so this is the redundant edge and we return it.

Example: edges = [[1,2],[1,3],[2,3]]. Edge [1,2] joins 1 and 2. Edge [1,3] joins 3 in too, so now 1, 2, 3 share one root. Edge [2,3]: both already have the same root, so the answer is [2, 3].

Because we process edges in input order, the first edge that closes a cycle is automatically the last valid answer, exactly what the problem asks for.

Time: O(n α(n)) Space: O(n)