2493. Divide Nodes Into the Maximum Number of Groups

Difficulty:
Hard
Related Topics:
    Similar Questions:

    Problem

    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:

    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:

    Solution (Java)

    class Solution {
    public static int magnificentSets(int n, int[][] edges) {
        // Make an array of adjacent nodes
        int[] degree = new int[n + 1];
        for (int[] edge : edges) {
            degree[edge[0]]++;
            degree[edge[1]]++;
        }
        int[][] adjacent = new int[n + 1][];
        for (int i = 1; i <= n; i++)
            adjacent[i] = new int[degree[i]];
        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            adjacent[a][--degree[a]] = b;
            adjacent[b][--degree[b]] = a;
        }
        // Find the largest distance from each node to other nodes in its component
        int[] queue = new int[n];
        int[] distance = new int[n + 1];
        int[] maxDistance = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(distance, -1);
            queue[0] = i;
            distance[i] = 0;
            int maxDist = 0;
            int first = 0;
            int last = 0;
            while (first <= last) {
                int node = queue[first++];
                int d = distance[node] + 1;
                for (int aNode : adjacent[node])
                    if (distance[aNode] < 0) {
                        distance[aNode] = d;
                        maxDist = d;
                        queue[++last] = aNode;
                    }
            }
            maxDistance[i] = maxDist;
        }
        // Split the graph into components, checking if it is bipartite
        // and adding the diameter of each component to the final result
        Arrays.fill(distance, -1);
        int result = 0;
        for (int i = 1; i <= n; i++) {
            if (distance[i] >= 0) // the node i is already examined
                continue;
            queue[0] = i;
            distance[i] = 0;
            int diameter = 0;
            int first = 0;
            int last = 0;
            while (first <= last) {
                int node = queue[first++];
                diameter = Math.max(diameter, maxDistance[node]);
                int d = distance[node] + 1;
                for (int aNode : adjacent[node]) {
                    int ad = distance[aNode];
                    if (ad < 0) {
                        distance[aNode] = d;
                        queue[++last] = aNode;
                    } else if ((d + ad) % 2 != 0) // the graph is not bipartite
                        return -1;
                }
            }
            result += diameter + 1;
        }
        return result;
    }
}

    Solution (Python3)

    class Solution:
  def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
    conn = defaultdict(set)
    for u, v in edges:
      conn[u].add(v)
      conn[v].add(u)

    def count_groups(root: int):
      if root not in conn:
        return 1, set([root])

      last, curr, nxt = set(), set([root]), set()
      groups = 0

      while curr:
        groups += 1

        for u in curr:
          # nodes in the same group can't be connected
          if u in nxt:
            # print('break 0:', root, groups, u)
            return -1, None

          addition = conn[u] - last
          if addition & curr:
            return -1, None

          nxt |= addition

        last |= curr
        curr, nxt = nxt, curr
        nxt.clear()

      return groups, last

    visited = set()
    cand = defaultdict(int)
    # print(cand)

    # for u in cand:
    for u in range(1, n+1):
      cnt, curr = count_groups(u)
      # print(u, cnt, len(conn[u]))

      if cnt > 0:
        idx = min(curr)
        cand[idx] = max(cand[idx], cnt)
        visited |= curr

    if len(visited) != n:
      return -1

    return sum(cand.values())

    Explain:

    nope.

    Complexity: