Redundant Connection II

hard union find graph

Problem

Rooted tree + one extra edge. Find the redundant edge to remove (last by input order if multiple).

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

Output[2,3]

Node 3 has two parents (1 and 2); remove the later one.

input

def find_redundant(edges):
    n = len(edges); parent = [0] * (n + 1); cand1 = cand2 = None
    for e in edges:
        if parent[e[1]] != 0: cand1 = [parent[e[1]], e[1]]; cand2 = e; e[0] = e[1] = -1
        else: parent[e[1]] = e[0]
    p = list(range(n + 1))
    def f(x):
        while p[x] != x: p[x] = p[p[x]]; x = p[x]
        return x
    for u, v in edges:
        if u < 0: continue
        ru, rv = f(u), f(v)
        if ru == rv: return cand1 if cand1 else [u, v]
        p[ru] = rv
    return cand2

function findRedundantDirectedConnection(edges) {
  const n = edges.length; const par = new Array(n + 1).fill(0); let c1 = null, c2 = null;
  const E = edges.map(e => e.slice());
  for (const e of E) {
    if (par[e[1]]) { c1 = [par[e[1]], e[1]]; c2 = e.slice(); e[0] = e[1] = -1; }
    else par[e[1]] = e[0];
  }
  const p = Array.from({length: n + 1}, (_, i) => i);
  const f = x => { while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; } return x; };
  for (const [u, v] of E) {
    if (u < 0) continue;
    const ru = f(u), rv = f(v);
    if (ru === rv) return c1 || [u, v];
    p[ru] = rv;
  }
  return c2;
}

int[] findRedundantDirectedConnection(int[][] edges) {
    int n = edges.length; int[] par = new int[n + 1], c1 = null, c2 = null;
    int[][] E = new int[n][]; for (int i = 0; i < n; i++) E[i] = edges[i].clone();
    for (int[] e : E) {
        if (par[e[1]] != 0) { c1 = new int[]{par[e[1]], e[1]}; c2 = e.clone(); e[0] = e[1] = -1; }
        else par[e[1]] = e[0];
    }
    int[] p = new int[n + 1]; for (int i = 0; i <= n; i++) p[i] = i;
    for (int[] e : E) {
        if (e[0] < 0) continue;
        int ru = find(p, e[0]), rv = find(p, e[1]);
        if (ru == rv) return c1 != null ? c1 : new int[]{e[0], e[1]};
        p[ru] = rv;
    }
    return c2;
}
int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }

int find(vector& p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }
vector findRedundantDirectedConnection(vector>& edges) {
    int n = edges.size(); vector par(n + 1, 0); vector c1, c2;
    auto E = edges;
    for (auto& e : E) {
        if (par[e[1]]) { c1 = {par[e[1]], e[1]}; c2 = e; e[0] = e[1] = -1; }
        else par[e[1]] = e[0];
    }
    vector p(n + 1); iota(p.begin(), p.end(), 0);
    for (auto& e : E) {
        if (e[0] < 0) continue;
        int ru = find(p, e[0]), rv = find(p, e[1]);
        if (ru == rv) return !c1.empty() ? c1 : vector{e[0], e[1]};
        p[ru] = rv;
    }
    return c2;
}

Explanation

We start with a rooted tree and one extra edge added, which breaks it in one of two ways: either some node ends up with two parents, or the extra edge forms a cycle (or both at once). The trick is to detect the two-parent case first, then use union-find to decide which edge to drop.

First pass: we scan edges and record for each node who points to it. If a node e[1] already has a parent, we have found a conflict — the earlier edge becomes cand1, the current one cand2, and we temporarily disable cand2 by setting e[0] = e[1] = -1.

Second pass: we run union-find over the edges, skipping the disabled one. If we hit a cycle (two endpoints already share a root), then disabling cand2 did not help — the culprit is cand1 (or just the cycle edge if no two-parent conflict existed). If no cycle appears, the disabled cand2 was the bad edge, so we return it.

This cleanly covers all three scenarios: pure cycle, pure two-parent, and the combined case.

Example: edges = [[1,2],[1,3],[2,3]]. Node 3 has two parents (1 and 3, then 2 and 3), so cand2 = [2,3]. Disabling it leaves a valid tree with no cycle, so the answer is [2,3].

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