Class Solution
java.lang.Object
g2401_2500.s2493_divide_nodes_into_the_maximum_number_of_groups.Solution
2493 - Divide Nodes Into the Maximum Number of Groups.<p>Hard</p>
<p>You are given a positive integer <code>n</code> representing the number of nodes in an <strong>undirected</strong> graph. The nodes are labeled from <code>1</code> to <code>n</code>.</p>
<p>You are also given a 2D integer array <code>edges</code>, where <code>edges[i] = [a<sub>i,</sub> b<sub>i</sub>]</code> indicates that there is a <strong>bidirectional</strong> edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code>. <strong>Notice</strong> that the given graph may be disconnected.</p>
<p>Divide the nodes of the graph into <code>m</code> groups ( <strong>1-indexed</strong> ) such that:</p>
<ul>
<li>Each node in the graph belongs to exactly one group.</li>
<li>For every pair of nodes in the graph that are connected by an edge <code>[a<sub>i,</sub> b<sub>i</sub>]</code>, if <code>a<sub>i</sub></code> belongs to the group with index <code>x</code>, and <code>b<sub>i</sub></code> belongs to the group with index <code>y</code>, then <code>|y - x| = 1</code>.</li>
</ul>
<p>Return <em>the maximum number of groups (i.e., maximum</em> <code>m</code><em>) into which you can divide the nodes</em>. Return <code>-1</code> <em>if it is impossible to group the nodes with the given conditions</em>.</p>
<p><strong>Example 1:</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2022/10/13/example1.png" alt="" /></p>
<p><strong>Input:</strong> n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]</p>
<p><strong>Output:</strong> 4</p>
<p><strong>Explanation:</strong> As shown in the image we:</p>
<ul>
<li>Add node 5 to the first group.</li>
<li>Add node 1 to the second group.</li>
<li>Add nodes 2 and 4 to the third group.</li>
<li>Add nodes 3 and 6 to the fourth group.</li>
</ul>
<p>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.</p>
<p><strong>Example 2:</strong></p>
<p><strong>Input:</strong> n = 3, edges = [[1,2],[2,3],[3,1]]</p>
<p><strong>Output:</strong> -1</p>
<p><strong>Explanation:</strong> 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.</p>
<p><strong>Constraints:</strong></p>
<ul>
<li><code>1 <= n <= 500</code></li>
<li><code>1 <= edges.length <= 10<sup>4</sup></code></li>
<li><code>edges[i].length == 2</code></li>
<li><code>1 <= a<sub>i</sub>, b<sub>i</sub> <= n</code></li>
<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
<li>There is at most one edge between any pair of vertices.</li>
</ul>
-
Constructor Summary
Constructors -
Method Summary
-
Constructor Details
-
Solution
public Solution()
-
-
Method Details
-
magnificentSets
public int magnificentSets(int n, int[][] edges)
-