Possible Bipartition
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
Constraints:
1 <= N <= 2000
0 <= dislikes.length <= 10000
dislikes[i].length == 2
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
There does not exist
i != j
for whichdislikes[i] == dislikes[j]
.
class Solution {
// Color -> 0 not colored YET
// Color -> 1 (one of the colors)
// Color -> -1 (The other color)
// colors array works as color storage as well as visited array
int[] colors;
List<Integer>[] graph;
public boolean possibleBipartition(int N, int[][] dislikes) {
// Creating adjacency list graph
graph = new ArrayList[N];
for (int i = 0; i < N; i++)
graph[i] = new ArrayList<>();
for (int[] pair : dislikes) {
graph[pair[0] - 1].add(pair[1] - 1);
graph[pair[1] - 1].add(pair[0] - 1);
}
colors = new int[N];
for (int i = 0; i < N; i++)
if (colors[i] == 0 && !paint(i, 1))
return false;
return true;
}
boolean paint(int u, int color) {
// "color" -> the color we want this person ("u") to be
if (colors[u] != 0)
return colors[u] == color;
colors[u] = color;
for (int neighbor : graph[u])
// If we cannot paint the neighbor with opposite color
if (!paint(neighbor, -color))
return false;
return true;
}
}
Last updated