# Divide Nodes Into the Maximum Number of Groups
**Difficulty:** HARD
[External](https://leetcode.com/problems/divide-nodes-into-the-maximum-number-of-groups)
Canonical: https://scaleengineer.com/dsa/problems/divide-nodes-into-the-maximum-number-of-groups
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Graph
---
## 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:

* 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:**

![](https://assets.glich.co/dsa/divide-nodes-into-the-maximum-number-of-groups/image0.png) 

**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.

# Approaches
## Backtracking Search
This approach attempts to solve the problem by exploring every possible assignment of nodes to groups. It uses a backtracking algorithm to systematically try all combinations. For each node, it tries to place it in a group and then recursively moves to the next node. If an assignment for all nodes is found that satisfies the given edge conditions, it calculates the number of groups used and updates a global maximum.
**Time:** O(n^n * E) · **Space:** O(n)
**Pros:** Conceptually straightforward and follows a standard brute-force pattern.
**Cons:** Extremely high time complexity, making it infeasible for the given constraints.; Will result in a 'Time Limit Exceeded' (TLE) error on most platforms.
### Explanation
The core idea of the backtracking approach is to build a valid group assignment for the nodes one by one. We can define a recursive function that takes the index of the node to be assigned and the current state of assignments.

For each node, we try to assign it to a group. After assigning a group, we recursively call the function for the next node. If we have assigned groups to all nodes, we check if the complete assignment is valid according to the problem's rules. If it is, we compute the number of groups used and update our answer. If at any point an assignment leads to a state where a valid solution is impossible (e.g., an edge constraint is violated with already placed nodes), we backtrack and try a different group.

While this approach is guaranteed to find the correct answer eventually, its search space is enormous. For `n` nodes and potentially `n` groups, the number of combinations is `n^n`, leading to an exponential time complexity that is not practical for the given constraints.
### Algorithm
*   Define a recursive function, say `solve(nodeIndex, assignments)`, where `assignments` stores the group for each assigned node.
*   **Base Case:** If `nodeIndex` is greater than `n`, all nodes have been assigned. Check if the current assignment is valid by iterating through all edges. If it is, update the maximum number of groups found so far. The number of groups is `max(assignments) - min(assignments) + 1`.
*   **Recursive Step:** For the current `nodeIndex`, iterate through all possible group numbers `g` (e.g., from 1 to `n`).
    *   Assign `nodeIndex` to group `g`.
    *   As a small optimization (pruning), check if this assignment violates the condition with any already-assigned neighbors. If it does, skip this group `g`.
    *   If the partial assignment is valid, make a recursive call: `solve(nodeIndex + 1, assignments)`.
    *   Backtrack by removing the assignment for `nodeIndex` before trying the next group.

## Bipartite Check and Diameter Calculation
This efficient approach leverages graph theory concepts. It understands that the condition `|y - x| = 1` for adjacent nodes implies that any valid grouping is impossible if the graph contains an odd-length cycle (i.e., is not bipartite). The problem can be solved independently for each connected component of the graph. For each component, we first check if it's bipartite. If not, we return -1. If it is, the maximum number of groups we can form within that component is equal to its diameter plus one. The final answer is the sum of the maximum groups for each component.
**Time:** O(V * (V + E)). For each component with `v_c` nodes and `e_c` edges, we do a bipartite check in `O(v_c + e_c)` and then `v_c` BFS runs for diameter, each taking `O(v_c + e_c)`. Summing over all components, the worst case is a single connected graph, leading to `O(V * (V + E))`. · **Space:** O(V + E) for the adjacency list, colors array, and BFS queue.
**Pros:** Correctly models the problem using graph properties.; Guaranteed to find the optimal solution.; Efficient enough to pass the given constraints.
**Cons:** The implementation is more complex than a simple brute-force approach.; The time complexity of O(V * (V + E)) might be too slow for significantly larger graphs, although it passes the given constraints.
### Explanation
A deeper analysis of the constraint `|group(u) - group(v)| = 1` for every edge `(u, v)` reveals key properties of the graph.

1.  **Bipartiteness:** This condition implies that adjacent nodes must have group numbers of different parity. This is the definition of a 2-coloring, which is possible only if the graph is bipartite (contains no odd-length cycles). If any connected component is not bipartite, no such grouping exists, and we must return -1.

2.  **Connected Components:** Since there are no edges between different connected components, we can solve the problem for each component independently and sum the results. If component `C1` can be divided into `m1` groups and `C2` into `m2` groups, we can assign groups `1...m1` to `C1` and `m1+1...m1+m2` to `C2`, for a total of `m1+m2` groups.

3.  **Diameter and Maximum Groups:** For a connected bipartite component, we can define a valid grouping by picking a starting node `s` and setting `group(u) = distance(s, u) + 1`. The number of groups will be `eccentricity(s) + 1`. To maximize the number of groups, we need to find a starting node `s` that maximizes this value. This is equivalent to finding the graph's diameter, which is the maximum eccentricity over all nodes. The maximum number of groups for a component is `diameter + 1`.

The overall algorithm is as follows:

```java
class Solution {
    public int magnificentSets(int n, int[][] edges) {
        List<Integer>[] adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }

        int[] colors = new int[n + 1]; // 0: uncolored, 1/-1: colors
        int totalMaxGroups = 0;

        for (int i = 1; i <= n; i++) {
            if (colors[i] == 0) { // New component
                List<Integer> componentNodes = new ArrayList<>();
                
                if (!isBipartiteAndCollectNodes(i, adj, colors, componentNodes)) {
                    return -1;
                }

                int maxLevels = 0;
                for (int startNode : componentNodes) {
                    int currentLevels = bfsToFindMaxLevel(startNode, adj, componentNodes);
                    maxLevels = Math.max(maxLevels, currentLevels);
                }
                totalMaxGroups += maxLevels;
            }
        }
        return totalMaxGroups;
    }

    private boolean isBipartiteAndCollectNodes(int startNode, List<Integer>[] adj, int[] colors, List<Integer> componentNodes) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(startNode);
        colors[startNode] = 1;
        
        componentNodes.add(startNode);
        int head = 0;

        while(head < componentNodes.size()){
            int u = componentNodes.get(head++);
            for(int v : adj[u]){
                if(colors[v] == 0){
                    colors[v] = -colors[u];
                    componentNodes.add(v);
                } else if (colors[v] == colors[u]){
                    return false; // Not bipartite
                }
            }
        }
        return true;
    }

    private int bfsToFindMaxLevel(int startNode, List<Integer>[] adj, List<Integer> componentNodes) {
        Queue<int[]> q = new LinkedList<>(); // {node, level}
        q.offer(new int[]{startNode, 1});
        
        Map<Integer, Integer> levels = new HashMap<>();
        levels.put(startNode, 1);
        
        int maxLevel = 0;

        while (!q.isEmpty()) {
            int[] current = q.poll();
            int u = current[0];
            int level = current[1];
            maxLevel = Math.max(maxLevel, level);

            for (int v : adj[u]) {
                if (!levels.containsKey(v)) {
                    levels.put(v, level + 1);
                    q.offer(new int[]{v, level + 1});
                }
            }
        }
        return maxLevel;
    }
}
```
### Algorithm
*   **Graph Representation:** Build an adjacency list for the graph from the `edges` array.
*   **Component Iteration:** Initialize `totalMaxGroups = 0` and a `colors` array (or `visited` array) of size `n+1` to keep track of visited nodes and their colors for the bipartite check.
*   **Iterate** through each node from `1` to `n`. If a node `i` has not been visited (`colors[i] == 0`), it signifies the start of a new connected component.
*   **Bipartite Check:** For each new component, perform a Breadth-First Search (BFS) or Depth-First Search (DFS) starting from node `i`.
    *   During the traversal, assign one of two colors (e.g., 1 and -1) to the nodes. If you find an edge `(u, v)` where both nodes have the same color, the graph contains an odd-length cycle and is not bipartite. In this case, no valid grouping is possible, so return -1.
    *   While performing this check, collect all nodes belonging to the current component into a list.
*   **Diameter Calculation:** If the component is bipartite, calculate its diameter. The diameter is the longest shortest path between any two nodes in the component.
    *   Initialize `componentDiameter = 0`.
    *   For each `startNode` in the component's node list, run a BFS to find the shortest distance to all other nodes in the component. The maximum distance found is the eccentricity of `startNode`.
    *   Update `componentDiameter` with the maximum eccentricity found among all nodes in the component.
*   **Aggregate Results:** The maximum number of groups for the current component is `componentDiameter + 1`. Add this value to `totalMaxGroups`.
*   **Final Result:** After iterating through all components, return `totalMaxGroups`.

# Solutions
### Java

```java
class Solution {
private
  List<Integer>[] g;
private
  List<Integer> arr = new ArrayList<>();
private
  boolean[] vis;
private
  int n;
public
  int magnificentSets(int n, int[][] edges) {
    g = new List[n + 1];
    this.n = n;
    Arrays.setAll(g, k->new ArrayList<>());
    for (var e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    vis = new boolean[n + 1];
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
      if (!vis[i]) {
        dfs(i);
        int t = -1;
        for (int v : arr) {
          t = Math.max(t, bfs(v));
        }
        if (t == -1) {
          return -1;
        }
        ans += t;
        arr.clear();
      }
    }
    return ans;
  }
private
  int bfs(int k) {
    int[] dist = new int[n + 1];
    Arrays.fill(dist, 1 << 30);
    dist[k] = 1;
    Deque<Integer> q = new ArrayDeque<>();
    q.offer(k);
    int ans = 1;
    while (!q.isEmpty()) {
      int i = q.pollFirst();
      for (int j : g[i]) {
        if (dist[j] == 1 << 30) {
          dist[j] = dist[i] + 1;
          ans = dist[j];
          q.offer(j);
        }
      }
    }
    for (int i : arr) {
      if (dist[i] == 1 << 30) {
        dist[i] = ++ans;
      }
    }
    for (int i : arr) {
      for (int j : g[i]) {
        if (Math.abs(dist[i] - dist[j]) != 1) {
          return -1;
        }
      }
    }
    return ans;
  }
private
  void dfs(int i) {
    arr.add(i);
    vis[i] = true;
    for (int j : g[i]) {
      if (!vis[j]) {
        dfs(j);
      }
    }
  }
}

```

### JavaScript

```javascript
var magnificentSets = function ( n , edges ) { const graph = Array . from ({ length : n + 1 }, () => new Set ()); for ( const [ u , v ] of edges ) { graph [ u ]. add ( v ); graph [ v ]. add ( u ); } const hash = new Map (); // 2. BFS for ( let i = 1 ; i <= n ; i ++ ) { let queue = [ i ]; const dis = Array ( n + 1 ). fill ( 0 ); dis [ i ] = 1 ; let mx = 1 , mn = n ; while ( queue . length ) { let next = []; for ( let u of queue ) { mn = Math . min ( mn , u ); for ( const v of graph [ u ]) { if ( ! dis [ v ]) { dis [ v ] = dis [ u ] + 1 ; mx = Math . max ( mx , dis [ v ]); next . push ( v ); } if ( Math . abs ( dis [ u ] - dis [ v ]) != 1 ) { return - 1 ; } } } queue = next ; } hash . set ( mn , Math . max ( mx , hash . get ( mn ) || 0 )); } let ans = 0 ; for ( const [ u , v ] of hash ) { ans += v ; } return ans ; };
```

### CPP

```cpp
class Solution {
public:
  int magnificentSets(int n, vector<vector<int>> &edges) {
    vector<vector<int>> g(n + 1);
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].emplace_back(b);
      g[b].emplace_back(a);
    }
    vector<int> arr;
    bool vis[n + 1];
    memset(vis, 0, sizeof vis);
    int ans = 0;
    function<void(int)> dfs = [&](int i) {
      arr.emplace_back(i);
      vis[i] = true;
      for (int &j : g[i]) {
        if (!vis[j]) {
          dfs(j);
        }
      }
    };
    auto bfs = [&](int k) {
      int ans = 1;
      int dist[n + 1];
      memset(dist, 0x3f, sizeof dist);
      dist[k] = 1;
      queue<int> q{{k}};
      while (!q.empty()) {
        int i = q.front();
        q.pop();
        for (int &j : g[i]) {
          if (dist[j] == 0x3f3f3f3f) {
            ans = dist[j] = dist[i] + 1;
            q.push(j);
          }
        }
      }
      for (int &i : arr) {
        if (dist[i] == 0x3f3f3f3f) {
          dist[i] = ++ans;
        }
      }
      for (int &i : arr) {
        for (int &j : g[i]) {
          if (abs(dist[i] - dist[j]) != 1) {
            return -1;
          }
        }
      }
      return ans;
    };
    for (int i = 1; i <= n; ++i) {
      if (!vis[i]) {
        dfs(i);
        int t = -1;
        for (int &v : arr)
          t = max(t, bfs(v));
        if (t == -1)
          return -1;
        ans += t;
        arr.clear();
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def magnificentSets(self, n: int, edges: List[List[int]]) -> int: def dfs(i): arr . append(i) vis[i] = True for j in g[i]: if not vis[j]: dfs(j) def bfs(i): ans = 1 dist = [inf] * (n + 1) dist[i] = 1 q = deque([i]) while q: i = q . popleft() for j in g[i]: if dist[j] == inf: ans = dist[j] = dist[i] + 1 q . append(j) for i in arr: if dist[i] == inf: ans += 1 dist[i] = ans for i in arr: for j in g[i]: if abs(dist[i] - dist[j]) != 1: return - 1 return ans g = defaultdict(list) for a, b in edges: g[a]. append(b) g[b]. append(a) vis = [False] * (n + 1) ans = 0 for i in range(1, n + 1): if not vis[i]: arr = [] dfs(i) t = max(bfs(v) for v in arr) if t == - 1: return - 1 ans += t return ans

```