#2493
Divide Nodes Into the Maximum Number of Groups
expert · 1050 · lc hard +32 · verified · 67% accepted · 986 likes · top 73%
Description
Given an undirected graph with n nodes (labeled 1 to n) and a bidirectional edge list edges (the graph may be disconnected), assign each node to exactly one of m numbered groups such that for every edge connecting nodes in groups x and y, |y - x| = 1. Return the maximum possible value of m, or -1 if no valid grouping exists.
Example 1:
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.
Code
1
2
3