Union Find structy

#coding-pattern #structy

https://structy.net/problems/premium/intro-to-union-find

union find - very performant when optimized
deals with connected components or "islands"

union nodes:

Pasted image 20250312222017.png

Not optimized solution:

const find = (roots, node) => {
  if (node === roots[node]) {
    return node;
  }

  return find(roots, roots[node]);
};

const union = (roots, nodeA, nodeB) => {
  const rootA = find(roots, nodeA);
  const rootB = find(roots, nodeB);
  roots[rootB] = rootA;
};

const countComponents = (n, edges) => {
  const roots = [];
  for (let i = 0; i < n; i += 1) {
    roots.push(i);
  }

  for (let edge of edges) {
    const [ nodeA, nodeB ] = edge;
    union(roots, nodeA, nodeB);  
  }

  let count = 0;
  for (let i = 0; i < n; i += 1) {
    if (i === roots[i]) {
      count += 1;
    }
  }

  return count;
};

Optimized code


const find = (roots, node) => {
  if (roots[node] === node) {
    return node;
  }

  const found = find(roots, roots[node]);
  roots[node] = found; //path compression
  return found;
};

const union = (roots, sizes, nodeA, nodeB) => {
  const rootA = find(roots, nodeA);
  const rootB = find(roots, nodeB);

  if (rootA === rootB) {
    return;
  }

  //union by size
  if (sizes[rootA] >= sizes[rootB]) {
    roots[rootB] = rootA;
    sizes[rootA] += sizes[rootB];
  } else {
    roots[rootA] = rootB;
    sizes[rootB] += sizes[rootA];
  }
};

const countComponents = (n, edges) => {
  const roots = [];
  const sizes = [];

  for (let i = 0; i < n; i += 1) {
    roots.push(i);
    sizes.push(1);
  }

  for (let edge of edges) {
    const [a, b] = edge;
    union(roots, sizes, a, b);
  }
  
  let count = 0;
  for (let i = 0; i < n; i += 1) {
    if (i === roots[i]) {
      count += 1;
    }
  }

  return count;
};

Problems: