Redundant Connection

Problem (restated)

Undirected graph that started as a tree of n nodes, then one extra edge was added. Return that redundant edge (the one that creates a cycle). If multiple answers, return the one that appears last in the input.

Intuition

Scan edges in order with Union-Find. The first edge whose endpoints share a root is the redundant one.

Approaches

export function findRedundantConnection(edges: number[][]): number[] {
  const n = edges.length;
  const parent = Array.from({ length: n + 1 }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  for (const e of edges) {
    const a = find(e[0]!), b = find(e[1]!);
    if (a === b) return e;
    parent[b] = a;
  }
  return [];
}

export function findRedundantConnection(edges: number[][]): number[] {
  const n = edges.length;
  const parent = Array.from({ length: n + 1 }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]!]!;
      x = parent[x]!;
    }
    return x;
  };
  for (const e of edges) {
    const a = find(e[0]!), b = find(e[1]!);
    if (a === b) return e;
    parent[b] = a;
  }
  return [];
}

Template connection

Union-Find cycle detection.

Reflection

• Union edges in the order given. The first edge whose ends already share a root is the redundant one. That is the earliest edge in the input, not an arbitrary edge of the cycle.
• The graph is a tree plus one edge. When several edges could close the cycle, input order decides which one is returned.
• A self-edge is a cycle at once. A single edge that does not close a cycle is not redundant.