2493. Divide Nodes Into the Maximum Number of Groups

Description

You are given a positive integer n representing the number of nodes in an undirected graph. The nodes are labeled from 1 to n.

You are also given a 2D integer array edges, where edges[i] = [ai, bi] indicates that there is a bidirectional edge between nodes ai and bi. Notice that the given graph may be disconnected.

Divide the nodes of the graph into m groups (1-indexed) such that:

• Each node in the graph belongs to exactly one group.
• For every pair of nodes in the graph that are connected by an edge [ai, bi], if ai belongs to the group with index x, and bi belongs to the group with index y, then |y - x| = 1.

Return the maximum number of groups (i.e., maximum m) into which you can divide the nodes. Return -1 if it is impossible to group the nodes with the given conditions.

 

Example 1:

Input: n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]
Output: 4
Explanation: As shown in the image we:
- Add node 5 to the first group.
- Add node 1 to the second group.
- Add nodes 2 and 4 to the third group.
- Add nodes 3 and 6 to the fourth group.
We can see that every edge is satisfied.
It can be shown that that if we create a fifth group and move any node from the third or fourth group to it, at least on of the edges will not be satisfied.

Example 2:

Input: n = 3, edges = [[1,2],[2,3],[3,1]]
Output: -1
Explanation: If we add node 1 to the first group, node 2 to the second group, and node 3 to the third group to satisfy the first two edges, we can see that the third edge will not be satisfied.
It can be shown that no grouping is possible.

 

Constraints:

• 1 <= n <= 500
• 1 <= edges.length <= 104
• edges[i].length == 2
• 1 <= ai, bi <= n
• ai != bi
• There is at most one edge between any pair of vertices.

 

Solutions

Solution: Union Find + Breadth-First Search

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
const magnificentSets = function (n, edges) {
  const graph = Array.from({ length: n + 1 }, () => []);
  const groups = Array.from({ length: n + 1 }, (_, index) => index);
  const ranks = Array.from({ length: n + 1 }, () => 0);

  const find = node => {
    const group = groups[node];

    return group === node ? node : find(group);
  };

  const union = (a, b) => {
    const x = find(a);
    const y = find(b);

    if (x === y) return;
    if (ranks[x] > ranks[y]) {
      groups[y] = x;
    } else if (ranks[y] > ranks[x]) {
      groups[x] = y;
    } else {
      groups[y] = x;
      ranks[x] += 1;
    }
  };

  for (const [a, b] of edges) {
    graph[a].push(b);
    graph[b].push(a);
    union(a, b);
  }

  const getGroupSize = node => {
    const stepMap = new Map();
    let queue = [node];
    let step = 0;

    stepMap.set(node, 0);

    while (queue.length) {
      const nextQueue = [];

      for (const nextNode of queue) {
        for (const neighbor of graph[nextNode]) {
          if (stepMap.has(neighbor)) {
            if (stepMap.get(neighbor) === step) return -1;
          } else {
            nextQueue.push(neighbor);
            stepMap.set(neighbor, step + 1);
          }
        }
      }
      step += 1;
      queue = nextQueue;
    }
    return step;
  };

  const groupNodes = Array.from({ length: n + 1 }, () => []);
  let result = 0;

  for (let node = 1; node <= n; node++) {
    const group = find(node);

    groupNodes[group].push(node);
  }

  for (const nodes of groupNodes) {
    let maxGroupSize = 0;

    for (const node of nodes) {
      const groupSize = getGroupSize(node);

      if (groupSize === -1) return -1;

      maxGroupSize = Math.max(groupSize, maxGroupSize);
    }
    result += maxGroupSize;
  }
  return result;
};