[JS] Union Find

n개의 노드는 0 ~ (n - 1)까지의 번호를 갖는다고 가정합니다.

class UnionFind {
  constructor(n) {
    this.parents = Array.from({ length: n }, (_, i) => i);
  }

  find(node) {
    if (this.parents[node] === node) return node;

    const parent = this.find(this.parents[node]);
    this.parents[node] = parent;

    return parent;
  }

  union(node1, node2) {
    const parent1 = this.find(node1);
    const parent2 = this.find(node2);

    this.parents[parent2] = parent1;
  }
}