Divide Nodes Into the Maximum Number of Groups — Hard Problem & Solution

Problem statement

An undirected graph has n nodes labelled 1 to n and the edges in edges (each [ai, bi]). The graph may be disconnected.

Split the nodes into m groups, indexed 1 to m, so that every node belongs to exactly one group and, for every edge [ai, bi], if ai is in group x and bi is in group y, then |y - x| == 1.

Return the maximum number of groups m for which such a split exists, or -1 if no split is possible.

Example 1

Input: n = 5, edges = [[1,2],[2,3],[3,4],[1,4],[5,2]]
Output: 4
Explanation: Groups {5}, {2}, {1,3}, {4}: every edge joins consecutive groups.

Example 2

Input: n = 5, edges = [[1,2],[3,4]]
Output: 5
Explanation: Each piece is laid out separately: {1},{2} then {3},{4} then {5}.

Example 3

Input: n = 4, edges = [[2,3],[3,4],[4,2],[1,2]]
Output: -1
Explanation: Nodes 2, 3, 4 form a triangle, and an odd cycle can never alternate between consecutive groups.

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

How to solve Divide Nodes Into the Maximum Number of Groups

Groups behave like BFS layers. For a bipartite component the best layering starts from the node with the greatest eccentricity, giving eccentricity + 1 groups; any edge inside a layer means an odd cycle and the answer is -1.

Approach

1. Label connected components.
2. From every node s, BFS and record the number of layers (maximum distance + 1). If an edge joins two nodes at the same distance, return -1.
3. For each component keep the maximum layer count over its nodes.
4. Return the sum over all components.

Why it works

In any valid grouping, adjacent nodes sit in consecutive groups, so the group numbers of a component span at most ecc(s) + 1 values when measured from the node s in the lowest group — distances bound the spread. BFS layering from s achieves exactly that bound and is valid whenever no edge stays inside a layer, which holds precisely for bipartite components. Separate components can occupy disjoint ranges of group indices, so their counts add.

Complexity

• Time — O(n · (n + m))
• Space — O(n + m)

Pitfalls

• Taking only one BFS per component (from an arbitrary node) can undercount — the start node matters.
• Remember isolated nodes: each contributes one group.
• Components are summed, not maximised.

Reference solution

Python

from typing import List
from collections import deque

def magnificentSets(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)
    comp = [0] * (n + 1)
    cid = 0
    for i in range(1, n + 1):
        if comp[i] == 0:
            cid += 1
            comp[i] = cid
            stack = [i]
            while stack:
                u = stack.pop()
                for v in adj[u]:
                    if comp[v] == 0:
                        comp[v] = cid
                        stack.append(v)
    best = [0] * (cid + 1)
    for s in range(1, n + 1):
        dist = [-1] * (n + 1)
        dist[s] = 0
        q = deque([s])
        far = 0
        while q:
            u = q.popleft()
            far = dist[u]
            for v in adj[u]:
                if dist[v] < 0:
                    dist[v] = dist[u] + 1
                    q.append(v)
                elif dist[v] == dist[u]:
                    return -1
        if far + 1 > best[comp[s]]:
            best[comp[s]] = far + 1
    return sum(best)

JavaScript

var magnificentSets = function(n, edges) {
    var adj = [];
    for (var i = 0; i <= n; i++) adj.push([]);
    for (var e = 0; e < edges.length; e++) {
        adj[edges[e][0]].push(edges[e][1]);
        adj[edges[e][1]].push(edges[e][0]);
    }
    var comp = [], cid = 0;
    for (var k = 0; k <= n; k++) comp.push(0);
    for (var r = 1; r <= n; r++) {
        if (comp[r] !== 0) continue;
        cid++;
        comp[r] = cid;
        var stack = [r];
        while (stack.length > 0) {
            var x = stack.pop();
            for (var j = 0; j < adj[x].length; j++) {
                var y = adj[x][j];
                if (comp[y] === 0) { comp[y] = cid; stack.push(y); }
            }
        }
    }
    var best = [];
    for (var c = 0; c <= cid; c++) best.push(0);
    for (var s = 1; s <= n; s++) {
        var dist = [];
        for (var t = 0; t <= n; t++) dist.push(-1);
        dist[s] = 0;
        var queue = [s], far = 0;
        for (var h = 0; h < queue.length; h++) {
            var u = queue[h];
            far = dist[u];
            for (var q = 0; q < adj[u].length; q++) {
                var v = adj[u][q];
                if (dist[v] < 0) { dist[v] = dist[u] + 1; queue.push(v); }
                else if (dist[v] === dist[u]) return -1;
            }
        }
        if (far + 1 > best[comp[s]]) best[comp[s]] = far + 1;
    }
    var total = 0;
    for (var b = 1; b <= cid; b++) total += best[b];
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More breadth-first search problems

• Minimum Cost to Make at Least One Valid Path in a Grid Hard
• Remove Max Number of Edges to Keep Graph Fully Traversable Hard
• Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree Hard
• Minimize Malware Spread Hard
• Sum of Distances in Tree Hard
• Shortest Cycle in a Graph Hard