Skip to content
Ayotl
Español

← Data structures from scratch · Lesson 29/32

Union-Find: are they in the same group?

✕
1/8

Everyone points to their boss

Union-Find (or disjoint sets) answers two things: merge two groups and find which group something belongs to. It's used for friend networks, for knowing whether two points on a map are connected, and in Kruskal's algorithm.

It all fits in a padre (parent) array: at first each element is its own parent (a group of one). Merging hangs one group's root under the other's root. Finding means climbing from parent to parent up to the root, which represents the group.

012345
leccion.js

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

  • The array ends up [1, 2, 2, 4, 4, 5]: 0 points to 1, 1 to 2, 3 to 4. The roots (2, 4 and 5) point to themselves, and they're the ones highlighted in the drawing.
  • 0 and 2 share a root: same group. 0 and 3 don't.
The whole lesson on one page

Everyone points to their boss

Union-Find (or disjoint sets) answers two things: merge two groups and find which group something belongs to. It's used for friend networks, for knowing whether two points on a map are connected, and in Kruskal's algorithm.

It all fits in a padre (parent) array: at first each element is its own parent (a group of one). Merging hangs one group's root under the other's root. Finding means climbing from parent to parent up to the root, which represents the group.

012345
const padre = [0, 1, 2, 3, 4, 5];

function encontrar(x) {
  while (padre[x] !== x) x = padre[x];
  return x;
}
function unir(a, b) {
  padre[encontrar(a)] = encontrar(b);
}

unir(0, 1);
unir(1, 2);
unir(3, 4);
console.log(padre);
console.log(encontrar(0) === encontrar(2));
console.log(encontrar(0) === encontrar(3));
  • The array ends up [1, 2, 2, 4, 4, 5]: 0 points to 1, 1 to 2, 3 to 4. The roots (2, 4 and 5) point to themselves, and they're the ones highlighted in the drawing.
  • 0 and 2 share a root: same group. 0 and 3 don't.

Two tricks: compress, and hang the small one

The simple version can form long chains (0→1→2→3→…), and then finding costs O(n). Two ideas fix it:

  • Path compression: when you find the root, every node on the way gets hung directly from it. Next time it's a single jump.
  • Union by size: the small group hangs from the big one, never the other way around, so the tree doesn't grow taller.

With both, each operation costs almost O(1) in practice (the real cost is the inverse Ackermann function, which never exceeds 4 for any size that fits in a computer).

function crear(n) {
  return { padre: Array.from({ length: n }, (_, i) => i), tam: new Array(n).fill(1) };
}

function encontrar(uf, x) {
  if (uf.padre[x] !== x) uf.padre[x] = encontrar(uf, uf.padre[x]);
  return uf.padre[x];
}

function unir(uf, a, b) {
  let ra = encontrar(uf, a), rb = encontrar(uf, b);
  if (ra === rb) return false;
  if (uf.tam[ra] < uf.tam[rb]) [ra, rb] = [rb, ra];
  uf.padre[rb] = ra;
  uf.tam[ra] += uf.tam[rb];
  return true;
}

const uf = crear(8);
unir(uf, 0, 1);
unir(uf, 2, 3);
unir(uf, 1, 3);
unir(uf, 4, 5);
console.log(uf.padre);

console.log(encontrar(uf, 3) === encontrar(uf, 0));
console.log(uf.padre);
console.log(unir(uf, 0, 2));
  • Before searching, 3 still points to 2 ([0, 0, 0, 2, …]).
  • After encontrar(uf, 3), 3 points straight to 0: that's path compression.
  • unir(uf, 0, 2) returns false: they were already in the same group, nothing to merge.

Counting groups

A classic use: you have people and a list of friendships, and you want to know how many friend groups there are (counting friends of friends). You start with n groups, and every unir that actually joins two groups subtracts one.

It's the same problem as counting islands on a map: each land cell is merged with its land neighbor, and at the end you count how many roots are left.

function crear(n) {
  return { padre: Array.from({ length: n }, (_, i) => i), tam: new Array(n).fill(1) };
}

function encontrar(uf, x) {
  if (uf.padre[x] !== x) uf.padre[x] = encontrar(uf, uf.padre[x]);
  return uf.padre[x];
}

function unir(uf, a, b) {
  let ra = encontrar(uf, a), rb = encontrar(uf, b);
  if (ra === rb) return false;
  if (uf.tam[ra] < uf.tam[rb]) [ra, rb] = [rb, ra];
  uf.padre[rb] = ra;
  uf.tam[ra] += uf.tam[rb];
  return true;
}

const nombres = ["Ana", "Beto", "Caro", "Dani", "Eli", "Fer"];
const amistades = [[0, 1], [1, 2], [3, 4]];

const uf = crear(nombres.length);
let grupos = nombres.length;
for (const [a, b] of amistades) {
  if (unir(uf, a, b)) grupos--;
}
console.log("grupos:", grupos);

const porRaiz = new Map();
nombres.forEach((nombre, i) => {
  const r = encontrar(uf, i);
  if (!porRaiz.has(r)) porRaiz.set(r, []);
  porRaiz.get(r).push(nombre);
});
console.log([...porRaiz.values()]);

Three groups: Ana, Beto and Caro (Ana and Caro aren't direct friends, but they share Beto); Dani and Eli; and Fer, alone.

Practice with a video challenge