Divide Nodes Into the Maximum Number of Groups
Problem
An undirected graph has n nodes labeled 1..n with the given edges (it may be disconnected). Put each node into one of m 1-indexed groups so that for every edge [a, b] the group indices differ by exactly 1. Return the maximum possible m, or -1 if no valid grouping exists.
n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]4n = 3, edges = [[1,2],[2,3],[3,1]]-1def maxGroups(n, edges):
g = [[] for _ in range(n + 1)]
for a, b in edges:
g[a].append(b); g[b].append(a)
def bfs(src):
dist = {src: 1}
q, far = [src], 1
while q:
u = q.pop(0)
for v in g[u]:
if v not in dist:
dist[v] = dist[u] + 1
far = max(far, dist[v])
q.append(v)
elif abs(dist[v] - dist[u]) != 1:
return -1
return far
seen, total = [False] * (n + 1), 0
for s in range(1, n + 1):
if seen[s]: continue
comp, stack = [], [s]
seen[s] = True
while stack:
u = stack.pop()
comp.append(u)
for v in g[u]:
if not seen[v]:
seen[v] = True; stack.append(v)
best = -1
for node in comp:
d = bfs(node)
if d == -1: return -1
best = max(best, d)
total += best
return totalfunction maxGroups(n, edges) {
const g = Array.from({ length: n + 1 }, () => []);
for (const [a, b] of edges) { g[a].push(b); g[b].push(a); }
function bfs(src) {
const dist = { [src]: 1 };
let q = [src], far = 1;
while (q.length) {
const nxt = [];
for (const u of q) for (const v of g[u]) {
if (dist[v] === undefined) {
dist[v] = dist[u] + 1;
far = Math.max(far, dist[v]);
nxt.push(v);
} else if (Math.abs(dist[v] - dist[u]) !== 1) return -1;
}
q = nxt;
}
return far;
}
const seen = new Array(n + 1).fill(false);
let total = 0;
for (let s = 1; s <= n; s++) {
if (seen[s]) continue;
const comp = [], stack = [s];
seen[s] = true;
while (stack.length) {
const u = stack.pop();
comp.push(u);
for (const v of g[u]) if (!seen[v]) { seen[v] = true; stack.push(v); }
}
let best = -1;
for (const node of comp) {
const d = bfs(node);
if (d === -1) return -1;
best = Math.max(best, d);
}
total += best;
}
return total;
}int maxGroups(int n, int[][] edges) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
boolean[] seen = new boolean[n + 1];
int total = 0;
for (int s = 1; s <= n; s++) {
if (seen[s]) continue;
List<Integer> comp = new ArrayList<>();
Deque<Integer> st = new ArrayDeque<>();
st.push(s); seen[s] = true;
while (!st.isEmpty()) {
int u = st.pop(); comp.add(u);
for (int v : g.get(u)) if (!seen[v]) { seen[v] = true; st.push(v); }
}
int best = -1;
for (int node : comp) {
int d = bfs(g, node);
if (d == -1) return -1;
best = Math.max(best, d);
}
total += best;
}
return total;
}
int bfs(List<List<Integer>> g, int src) {
Map<Integer, Integer> dist = new HashMap<>();
dist.put(src, 1);
Queue<Integer> q = new LinkedList<>(); q.add(src);
int far = 1;
while (!q.isEmpty()) {
int u = q.poll();
for (int v : g.get(u)) {
if (!dist.containsKey(v)) {
dist.put(v, dist.get(u) + 1);
far = Math.max(far, dist.get(v));
q.add(v);
} else if (Math.abs(dist.get(v) - dist.get(u)) != 1) return -1;
}
}
return far;
}int bfs(vector<vector<int>>& g, int src) {
unordered_map<int, int> dist;
dist[src] = 1;
queue<int> q; q.push(src);
int far = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (!dist.count(v)) {
dist[v] = dist[u] + 1;
far = max(far, dist[v]);
q.push(v);
} else if (abs(dist[v] - dist[u]) != 1) return -1;
}
}
return far;
}
int maxGroups(int n, vector<vector<int>>& edges) {
vector<vector<int>> g(n + 1);
for (auto& e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
vector<bool> seen(n + 1, false);
int total = 0;
for (int s = 1; s <= n; s++) {
if (seen[s]) continue;
vector<int> comp, st = {s};
seen[s] = true;
while (!st.empty()) {
int u = st.back(); st.pop_back(); comp.push_back(u);
for (int v : g[u]) if (!seen[v]) { seen[v] = true; st.push_back(v); }
}
int best = -1;
for (int node : comp) {
int d = bfs(g, node);
if (d == -1) return -1;
best = max(best, d);
}
total += best;
}
return total;
}Explanation
The grouping rule says every edge must join nodes whose group indices differ by exactly 1. If you fix a starting node in group 1 and walk outward, each step must move to an adjacent group — that is precisely a BFS layering, where a node's layer is its shortest-path distance (in edges) from the root, plus one.
A layering is valid only if every edge connects two consecutive layers. If any edge links two nodes in the same layer, an odd cycle exists, the graph is not bipartite, and the answer is -1. The BFS checks this on the fly: when it meets an already-seen neighbor whose distance differs by anything other than 1, it bails out.
For a single connected component, the number of groups produced by one BFS equals the largest layer reached. To maximize groups we try BFS from every node as the root and keep the deepest layering — this is the component's diameter expressed in layers.
The graph may be disconnected, and components are independent: shifting one component's group numbers never touches another's. So we sum the best layer count over all components. Any component containing an odd cycle forces the whole answer to -1.
Example: from root 5 the layers are {5}, {1}, {2,4}, {3,6} — four groups, and no edge violates the rule, so the component contributes 4. With a single component that is the final answer.