Divide Nodes Into the Maximum Number of Groups

export function magnificentSets(n: number, edges: number[][]): number {
  const disjointSet = new DisjointSet(n);
  const graph: number[][] = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    graph[a - 1].push(b - 1);
    graph[b - 1].push(a - 1);
    disjointSet.union(a - 1, b - 1);
  }
 
  const groupSizes = new Map<number, number>();
  for (let node = 0; node < n; node++) {
    const groupSize = getGroupSize(n, graph, node);
    if (groupSize === -1) {
      return -1;
    }
    const rootNode = disjointSet.find(node);
    groupSizes.set(rootNode, Math.max(groupSizes.get(rootNode) ?? 0, groupSize));
  }
 
  return [...groupSizes.values()].reduce((acc, groupSize) => acc + groupSize, 0);
}
 
function getGroupSize(n: number, graph: number[][], node: number): number {
  const prevDepth: number[] = new Array(n).fill(-1);
  prevDepth[node] = 0;
 
  let depth = 0;
  let queue = [node];
  while (0 < queue.length) {
    const nextQueue: number[] = [];
    for (const node of queue) {
      for (const neighbor of graph[node]) {
        if (prevDepth[neighbor] === -1) {
          prevDepth[neighbor] = depth + 1;
          nextQueue.push(neighbor);
        } else if (prevDepth[neighbor] === depth) {
          return -1;
        }
      }
    }
    queue = nextQueue;
    depth += 1;
  }
  return depth;
}
 
class DisjointSet {
  private readonly parent: number[];
  private readonly depth: number[];
 
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.depth = new Array(n).fill(0);
  }
 
  find(node: number): number {
    if (this.parent[node] === node) {
      return node;
    }
    this.parent[node] = this.find(this.parent[node]);
    return this.parent[node];
  }
 
  union(node1: number, node2: number): void {
    const parent1 = this.find(node1);
    const parent2 = this.find(node2);
    if (parent1 === parent2) {
      return;
    }
    if (this.depth[parent1] <= this.depth[parent2]) {
      this.parent[parent2] = parent1;
    } else {
      this.parent[parent1] = parent2;
    }
    if (this.depth[parent1] === this.depth[parent2]) {
      this.depth[parent1] += 1;
    }
  }
}