possible-bipartition

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

We want to split a group of <code>n</code> people (labeled from <code>1</code> to <code>n</code>) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.

Given the integer <code>n</code> and the array <code>dislikes</code> where <code>dislikes[i] = [ai, bi]</code> indicates that the person labeled <code>ai</code> does not like the person labeled <code>bi</code>, return <code>true</code> if it is possible to split everyone into two groups in this way.

&nbsp;
Example 1:

<pre>
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: The first group has [1,4], and the second group has [2,3].
</pre>

Example 2:

<pre>
Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 2000</code></li>
	<li><code>0 &lt;= dislikes.length &lt;= 104</code></li>
	<li><code>dislikes[i].length == 2</code></li>
	<li><code>1 &lt;= ai &lt; bi &lt;= n</code></li>
	<li>All the pairs of <code>dislikes</code> are unique.</li>
</ul>

possibleBipartition

Possible Bipartition

Depth-First Search

Breadth-First Search

Union Find

Graph

给定一组&nbsp;<code>n</code>&nbsp;人（编号为&nbsp;<code>1, 2, ..., n</code>），&nbsp;我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。

给定整数 <code>n</code>&nbsp;和数组 <code>dislikes</code>&nbsp;，其中&nbsp;<code>dislikes[i] = [ai, bi]</code>&nbsp;，表示不允许将编号为 <code>ai</code>&nbsp;和&nbsp;&nbsp;<code>bi</code>的人归入同一组。当可以用这种方法将所有人分进两组时，返回 <code>true</code>；否则返回 <code>false</code>。

&nbsp;

<ol>
</ol>

示例 1：

<pre>
输入：n = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
解释：group1 [1,4], group2 [2,3]
</pre>

示例 2：

<pre>
输入：n = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false
</pre>

示例 3：

<pre>
输入：n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出：false
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 2000</code></li>
	<li><code>0 &lt;= dislikes.length &lt;= 104</code></li>
	<li><code>dislikes[i].length == 2</code></li>
	<li><code>1 &lt;= dislikes[i][j] &lt;= n</code></li>
	<li><code>ai&nbsp;&lt; bi</code></li>
	<li><code>dislikes</code>&nbsp;中每一组都 不同</li>
</ul>

&nbsp;