divide-nodes-into-the-maximum-number-of-groups

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a positive integer <code>n</code> representing the number of nodes in an undirected graph. The nodes are labeled from <code>1</code> to <code>n</code>.

You are also given a 2D integer array <code>edges</code>, where <code>edges[i] = [ai, bi]</code> indicates that there is a bidirectional edge between nodes <code>ai</code> and <code>bi</code>. Notice that the given graph may be disconnected.

Divide the nodes of the graph into <code>m</code> groups (1-indexed) such that:

<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>[ai, bi]</code>, if <code>ai</code> belongs to the group with index <code>x</code>, and <code>bi</code> belongs to the group with index <code>y</code>, then <code>|y - x| = 1</code>.</li>
</ul>

Return the maximum number of groups (i.e., maximum <code>m</code>) into which you can divide the nodes. Return <code>-1</code> if it is impossible to group the nodes with the given conditions.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/13/example1.png" style="width: 352px; height: 201px;" />
<pre>
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.
</pre>

Example 2:

<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>1 &lt;= edges.length &lt;= 104</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= ai, bi &lt;= n</code></li>
	<li><code>ai != bi</code></li>
	<li>There is at most one edge between any pair of vertices.</li>
</ul>

magnificentSets

Divide Nodes Into the Maximum Number of Groups

Binary Tree Level Order Traversal

binary-tree-level-order-traversal

二叉树的层序遍历

Is Graph Bipartite?

is-graph-bipartite

判断二分图

Shortest Cycle in a Graph

shortest-cycle-in-a-graph

图中的最短环

Depth-First Search

Breadth-First Search

Union Find

Graph

给你一个正整数&nbsp;<code>n</code>&nbsp;，表示一个 无向&nbsp;图中的节点数目，节点编号从&nbsp;<code>1</code>&nbsp;到&nbsp;<code>n</code>&nbsp;。

同时给你一个二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [ai, bi]</code>&nbsp;表示节点&nbsp;<code>ai</code> 和&nbsp;<code>bi</code>&nbsp;之间有一条&nbsp;双向&nbsp;边。注意给定的图可能是不连通的。

请你将图划分为&nbsp;<code>m</code>&nbsp;个组（编号从 1&nbsp;开始），满足以下要求：

<ul>
	<li>图中每个节点都只属于一个组。</li>
	<li>图中每条边连接的两个点&nbsp;<code>[ai, bi]</code>&nbsp;，如果&nbsp;<code>ai</code>&nbsp;属于编号为&nbsp;<code>x</code>&nbsp;的组，<code>bi</code>&nbsp;属于编号为&nbsp;<code>y</code>&nbsp;的组，那么&nbsp;<code>|y - x| = 1</code>&nbsp;。</li>
</ul>

请你返回最多可以将节点分为多少个组（也就是最大的&nbsp;<code>m</code>&nbsp;）。如果没办法在给定条件下分组，请你返回&nbsp;<code>-1</code>&nbsp;。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2022/10/13/example1.png" style="width: 352px; height: 201px;">

<pre>输入：n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]
输出：4
解释：如上图所示，
- 节点 5 在第一个组。
- 节点 1 在第二个组。
- 节点 2 和节点 4 在第三个组。
- 节点 3 和节点 6 在第四个组。
所有边都满足题目要求。
如果我们创建第五个组，将第三个组或者第四个组中任何一个节点放到第五个组，至少有一条边连接的两个节点所属的组编号不符合题目要求。
</pre>

示例 2：

<pre>输入：n = 3, edges = [[1,2],[2,3],[3,1]]
输出：-1
解释：如果我们将节点 1 放入第一个组，节点 2 放入第二个组，节点 3 放入第三个组，前两条边满足题目要求，但第三条边不满足题目要求。
没有任何符合题目要求的分组方式。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>1 &lt;= edges.length &lt;= 104</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= ai, bi &lt;= n</code></li>
	<li><code>ai != bi</code></li>
	<li>两个点之间至多只有一条边。</li>
</ul>