Amazon

eBay

2020-05-27

## 886. Possible Bipartition

### Question:

Given a set of `N` people (numbered `1, 2, ..., N`), we would like to split everyone into two groups of any size.

Each person may dislike some other people, and they should not go into the same group.

Formally, if `dislikes[i] = [a, b]`, it means it is not allowed to put the people numbered `a` and `b` into the same group.

Return `true` if and only 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: group1 [1,4], group2 [2,3]
``````

#### Example 2:

``````Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
``````

#### Example 3:

``````Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false
``````

Note:

1. `1 <= N <= 2000`
2. `0 <= dislikes.length <= 10000`
3. `1 <= dislikes[i][j] <= N`
4. `dislikes[i] < dislikes[i]`
5. There does not exist `i != j` for which `dislikes[i] == dislikes[j]`.

### Solution:

Similar to LeetCode Question 785, color each node with a color. The neighbours node should have a different color than yours. Then using BFS or DFS to check or assign the color to the node next to it.

The following picture demo borrowed from Huahua. Using BFS:

``````class Solution {
public boolean possibleBipartition(int N, int[][] dislikes) {
if (dislikes == null || dislikes.length == 0) return true;
HashMap<Integer, Set<Integer>> map = new HashMap<>();
for (int[] i : dislikes) {
int a = i;
int b = i;
map.putIfAbsent(a, new HashSet<Integer>());
map.putIfAbsent(b, new HashSet<Integer>());
}

Queue<Integer> que = new LinkedList<>();
int[] colors = new int[N + 1];

for (int i = 1; i <= N; i++) {
if (colors[i] != 0) continue;

colors[i] = 1;
que.offer(i);

while (!que.isEmpty()) {
int index = que.poll();
if (!map.containsKey(index)) continue;
for (int next: map.get(index)){
if (colors[next] == colors[index]) {
return false;
}
if(colors[next] == 0) {
colors[next] = -colors[index];
que.offer(next);
}
}
}
}
return true;
}
}
``````

Using DFS:

``````class Solution {

public int[] colors;
public HashMap<Integer, Set<Integer>> map;

public boolean possibleBipartition(int N, int[][] dislikes) {
if (dislikes == null || dislikes.length == 0) return true;
map = new HashMap<>();
for (int[] i : dislikes) {
int a = i;
int b = i;
map.putIfAbsent(a, new HashSet<Integer>());
map.putIfAbsent(b, new HashSet<Integer>());
}

colors = new int[N + 1];
for (int i = 1; i <= N; i++) {
if (colors[i] == 0 && !dfs(i, 1)) return false;
}
return true;
}

private boolean dfs(int i, int targetcolor) {
if (colors[i] != 0) return colors[i] == targetcolor;

colors[i] = targetcolor;

if (map.get(i) == null) return true;

for (int next : map.get(i)) {
if (!dfs(next, -targetcolor)) return false;
}

return true;
}
}
``````

Time complexity: O(V+E)
Space complexity: O(V+E)