Why does this union-find cycle check miss some redundant edges?

programming web dev
1

I’m using union-find to detect the first edge that creates a cycle in an undirected graph, but this sometimes returns null even when a cycle exists. I suspect the issue is in how parents are updated during union. What is wrong here?

function hasCycle(edges, n) {
  const p = Array.from({ length: n }, (_, i) => i);
  const find = x => p[x] === x ? x : find(p[x]);
  for (const [a, b] of edges) {
    if (find(a) === find(b)) return [a, b];
    p[a] = b;
  }
  return null;
}

Quelly

2

@Quelly, the bad line is `p[a] = b

because it links raw vertices instead of linking the two set roots, so earlier structure can get overwritten and the cycle check goes blind;
a quick debug signal is printing

find(a), find(b), p.slice()` after each edge and you’ll see parents stop representing components.

Ellen :blush: