HardBreadth-First SearchUnion FindGraph

Divide Nodes Into the Maximum Number of Groups

1 approach, code in every language

You are given a positive integer n representing nodes numbered from 1 to n, and an undirected graph given by edges where edges[i] = [ai, bi] connects nodes ai and bi.

You must place each node into one of several numbered groups (groups start at 1) so that for every edge [ai, bi], the two endpoints land in groups whose numbers differ by exactly one. Not every group number needs to be used, but the assignment must respect this adjacency rule for all edges.

Return the maximum number of groups into which the nodes can be divided. If no valid assignment exists, return -1.

Example 1

Input: n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]

Output: 4

Assigning groups as node 5 -> 1, nodes 1 and 6 -> 2, nodes 2 and 4 -> 3, node 3 -> 4 keeps every edge between consecutively numbered groups, using 4 groups in total.

Example 2

Input: n = 3, edges = [[1,2],[2,3],[3,1]]

Output: -1

The three nodes form an odd cycle (a triangle), which is not bipartite, so no valid group layering exists.

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

Bipartite Check + BFS Layering

Verify each component is bipartite, then BFS from every node to find the deepest valid layering per component and sum the best depths.

Loading animation…

Intuition

The adjacent-group rule means neighboring nodes always sit one level apart, which is only possible if the graph contains no odd cycle - that is, every connected component must be bipartite. If any component fails the 2-coloring test, we return -1. When a component is bipartite, running a BFS from a chosen node produces layers where each edge spans consecutive layers, so the number of layers equals the group count for that start. To maximize groups, we try starting the BFS from every node in the component and keep the largest layer depth found. Summing the best depth of each independent component gives the overall maximum.

Algorithm walkthrough

1Build an undirected adjacency list and a color array to test bipartiteness while collecting the nodes of each component.
2For each uncolored node, BFS and alternate colors; if an edge joins two same-colored nodes, the component is not bipartite, so return -1.
3For a bipartite component, run a separate BFS from each of its nodes, recording the maximum layer index reached (distance + 1).
4Take the largest layer depth over all start nodes in that component as its best group count.
5Add each component's best depth to a running total.
6Return the total, which is the maximum number of groups across the whole graph.

Implementation

from collections import deque
from typing import List

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

        def bfs_depth(source: int) -> int:
            dist = [0] * (n + 1)
            dist[source] = 1
            queue = deque([source])
            max_dist = 1
            while queue:
                node = queue.popleft()
                for neighbor in adj[node]:
                    if dist[neighbor] == 0:
                        dist[neighbor] = dist[node] + 1
                        max_dist = max(max_dist, dist[neighbor])
                        queue.append(neighbor)
            return max_dist

        color = [0] * (n + 1)
        components = []
        for start in range(1, n + 1):
            if color[start] != 0:
                continue
            color[start] = 1
            queue = deque([start])
            comp = [start]
            while queue:
                node = queue.popleft()
                for neighbor in adj[node]:
                    if color[neighbor] == 0:
                        color[neighbor] = -color[node]
                        comp.append(neighbor)
                        queue.append(neighbor)
                    elif color[neighbor] == color[node]:
                        return -1
            components.append(comp)

        total = 0
        for comp in components:
            best = 0
            for node in comp:
                best = max(best, bfs_depth(node))
            total += best
        return total

Time

O(V * (V + E))

Space

O(V + E)

For each component we launch a BFS from every one of its nodes, so the layering pass dominates the runtime.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Stacking Relay Masts Into Tiers is our own problem on the technique behind Divide Nodes Into the Maximum Number of Groups: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free