Union-Find With Path Compression

export class UnionFind<T> {
  private readonly parent = new Map<T, T>();
  private readonly rank = new Map<T, number>();
  private readonly sizes = new Map<T, number>();

  public add(value: T): this {
    if (!this.parent.has(value)) {
      this.parent.set(value, value);
      this.rank.set(value, 0);
      this.sizes.set(value, 1);
    }
    return this;
  }

  public find(value: T): T {
    if (!this.parent.has(value)) {
      throw new RangeError("unknown union-find value");
    }
    let root = value;
    while (this.parent.get(root) !== root) {
      root = this.parent.get(root) as T;
    }
    let current = value;
    while (current !== root) {
      const next = this.parent.get(current) as T;
      this.parent.set(current, root);
      current = next;
    }
    return root;
  }

  public union(left: T, right: T): boolean {
    let leftRoot = this.find(left);
    let rightRoot = this.find(right);
    if (leftRoot === rightRoot) return false;

    if ((this.rank.get(leftRoot) ?? 0) < (this.rank.get(rightRoot) ?? 0)) {
      [leftRoot, rightRoot] = [rightRoot, leftRoot];
    }
    this.parent.set(rightRoot, leftRoot);
    this.sizes.set(
      leftRoot,
      (this.sizes.get(leftRoot) ?? 0) + (this.sizes.get(rightRoot) ?? 0),
    );
    this.sizes.delete(rightRoot);
    if (
      (this.rank.get(leftRoot) ?? 0) === (this.rank.get(rightRoot) ?? 0)
    ) {
      this.rank.set(leftRoot, (this.rank.get(leftRoot) ?? 0) + 1);
    }
    return true;
  }

  public connected(left: T, right: T): boolean {
    return this.find(left) === this.find(right);
  }

  public componentSize(value: T): number {
    return this.sizes.get(this.find(value)) ?? 0;
  }

  public get count(): number {
    let roots = 0;
    for (const [value, parent] of this.parent) {
      if (value === parent) roots += 1;
    }
    return roots;
  }

  public groups(): T[][] {
    const grouped = new Map<T, T[]>();
    for (const value of this.parent.keys()) {
      const root = this.find(value);
      const bucket = grouped.get(root);
      if (bucket === undefined) {
        grouped.set(root, [value]);
      } else {
        bucket.push(value);
      }
    }
    return [...grouped.values()];
  }
}

const unionFind = new UnionFind<string>();
for (const name of ["ada", "grace", "linus", "margaret", "alan"]) {
  unionFind.add(name);
}
unionFind.union("ada", "grace");
unionFind.union("grace", "linus");
unionFind.union("margaret", "alan");

console.log(unionFind.connected("ada", "linus"));
console.log(unionFind.connected("ada", "alan"));
console.log(unionFind.componentSize("linus"));
console.log(unionFind.count);
console.log(unionFind.groups());

try {
  unionFind.find("unknown");
} catch (error) {
  console.log(error instanceof Error ? error.message : String(error));
}