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 <= 20000 <= dislikes.length <= 104dislikes[i].length == 21 <= ai < bi <= n- All the pairs of
dislikesare 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[0], k -> new ArrayList<>()).add(dislike[1]);
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<>();
queue.add(node);
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];
queue.add(neighbor);
}
}
}
return true;
}
}
Input
Output
#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
}
Input
Output
#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:
disliked[a].add(b)
disliked[b].add(a)
for i in range(1, N + 1):
if group[i] == i and not self.merge(i, 2001, group, disliked): return False
return True
Input
Output
#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;
colors.Add(i, color);
foreach (var j in graph[i])
if (!DFS(j, color ^ 1, graph, colors))
return false;
return true;
}
}
}
Input
Output