> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Divide Nodes Into the Maximum Number of Groups

> Tested Python solution for LeetCode 2493 with 19 pytest cases. Generate a practice environment with lcpy.

LeetCode 2493, [Hard](/catalog/hard). Topics: [Breadth-First Search](/catalog/topics/breadth-first-search), [Depth-First Search](/catalog/topics/depth-first-search), [Union Find](/catalog/topics/union-find), [Graph](/catalog/topics/graph). [View on LeetCode](https://leetcode.com/problems/divide-nodes-into-the-maximum-number-of-groups/description/).

Generate this problem as a practice environment: tested reference solution, 19 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2493   # by problem number
lcpy gen -s divide_nodes_into_the_maximum_number_of_groups   # by problem name
```

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

### Examples

![Example 1](https://assets.leetcode.com/uploads/2022/10/13/example1.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 if we create a fifth group and move any node from the third or fourth group to it, at least one of the edges will not be satisfied.
```

```
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 <= 10^4`
* `edges[i].length == 2`
* `1 <= ai, bi <= n`
* `ai != bi`
* There is at most one edge between any pair of vertices.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/divide_nodes_into_the_maximum_number_of_groups/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/divide_nodes_into_the_maximum_number_of_groups/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class Solution:
    # Time: O(n * (n + e)) where e = len(edges)
    # Space: O(n + e)

    def magnificent_sets(self, n: int, edges: list[list[int]]) -> int:
        adj: list[list[int]] = [[] for _ in range(n + 1)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)

        seen: list[bool] = [False] * (n + 1)
        total = 0
        for start in range(1, n + 1):
            if seen[start]:
                continue
            component = self._collect(start, adj, seen)
            best = 0
            for source in component:
                groups = self._max_groups(source, adj)
                if groups < 0:
                    return -1
                best = max(best, groups)
            total += best
        return total

    def _collect(self, start: int, adj: list[list[int]], seen: list[bool]) -> list[int]:
        component = [start]
        seen[start] = True
        stack = [start]
        while stack:
            node = stack.pop()
            for nxt in adj[node]:
                if not seen[nxt]:
                    seen[nxt] = True
                    component.append(nxt)
                    stack.append(nxt)
        return component

    def _max_groups(self, source: int, adj: list[list[int]]) -> int:
        # BFS layer count from source; -1 when an intra-layer edge breaks bipartiteness
        depth: dict[int, int] = {source: 0}
        queue: deque[int] = deque([source])
        max_depth = 0
        while queue:
            node = queue.popleft()
            for nxt in adj[node]:
                if nxt not in depth:
                    depth[nxt] = depth[node] + 1
                    max_depth = max(max_depth, depth[nxt])
                    queue.append(nxt)
                elif depth[nxt] == depth[node]:
                    return -1
        return max_depth + 1
```

## Complexity

| Time | Space |
| - | - |
| O(n \* (n + e)) where e = len(edges) | O(n + e) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.