Algorithm

Problem Name: 886. Possible Bipartition

We want to split a group of `n` people (labeled from `1` to `n`) 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 `n` and the array `dislikes` where `dislikes[i] = [ai, bi]` indicates that the person labeled `ai` does not like the person labeled `bi`, return `true` if it is possible to split everyone into two groups in this way.

Example 1:

```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].
```

Example 2:

```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.
```

Constraints:

• `1 <= n <= 2000`
• `0 <= dislikes.length <= 104`
• `dislikes[i].length == 2`
• `1 <= ai < bi <= n`
• All the pairs of `dislikes` are unique.

Code Examples

#1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
Map();
for (int[] dislike : dislikes) {
map.computeIfAbsent(dislike[1], k -> new ArrayList < >()).add(dislike[0]);
}
int[] color = new int[n + 1];
Arrays.fill(color, -1);
for (int i = 1; i  < = n; i++) {
if (color[i] == -1) {
if (!bfs(i, map, color)) {
return false;
}
}
}
return true;
}

private boolean bfs(int node, Map < Integer, List queue = new LinkedList<>();
color[node] = 0;
while (!queue.isEmpty()) {
int removed = queue.remove();
for (Integer neighbor : map.getOrDefault(removed, new ArrayList < >())) {
if (color[neighbor] == color[removed]) {
return false;
}
if (color[neighbor] == -1) {
color[neighbor] = 1 - color[removed];
}
}
}
return true;
}
}
``````
Copy The Code &

Input

cmd
n = 4, dislikes = [[1,2],[1,3],[2,4]]

Output

cmd
true

#2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const possibleBipartition = function (N, dislikes) {
const graph = []
for (let i = 0; i  < = N; i++) {
graph[i] = []
}
for (let el of dislikes) {
graph[el[0]].push(el[1])
graph[el[1]].push(el[0])
}
const color = new Array(N + 1).fill(0)
for (let i = 1; i  < = N; i++) {
if (color[i] == 0) {
color[i] = 1
const q = []
q.push(i)
while (q.length > 0) {
let cur = q.shift()
for (let j of graph[cur]) {
if (color[j] == 0) {
color[j] = color[cur] == 1 ? 2 : 1
q.push(j)
} else {
if (color[j] == color[cur]) return false
}
}
}
}
}
return true
}
``````
Copy The Code &

Input

cmd
n = 4, dislikes = [[1,2],[1,3],[2,4]]

Output

cmd
true

#3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def merge(self, node, p, group, disliked):
group[node] = p
for v in disliked[node]:
if group[v] == p or (group[v] == v and not self.merge(v, -p, group, disliked)): return False
return True

def possibleBipartition(self, N, dislikes):
group, disliked = [i for i in range(N + 1)], collections.defaultdict(set)
for a, b in dislikes:
for i in range(1, N + 1):
if group[i] == i and not self.merge(i, 2001, group, disliked): return False
return True
``````
Copy The Code &

Input

cmd
n = 3, dislikes = [[1,2],[1,3],[2,3]]

Output

cmd
false

#4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0886_PossibleBipartition
{
public bool PossibleBipartition(int N, int[][] dislikes)
{
var colors = new Dictionary < int, int>();
var graph = new List colors)
{
if (colors.ContainsKey(i))
return colors[i] == color;

foreach (var j in graph[i])
if (!DFS(j, color ^ 1, graph, colors))
return false;

return true;
}
}
}
``````
Copy The Code &

Input

cmd
n = 3, dislikes = [[1,2],[1,3],[2,3]]

Output

cmd
false