Leetcode 886. Possible Bipartition
Problem Explanation
Given a set of N people numbered sequentially from 1 to N, we need to split them up into two groups. However, the restriction here is that, if person A dislikes person B, then person A and person B cannot be in the same group.
For example, let's assume we have 4 people and dislikes[][] = [[1, 2], [1, 3], [2, 4]], it implies that people 2 and 3 are disliked by person 1, and person 4 is disliked by person 2. It's possible to arrange them in two groups: group 1 - people 1 and 4; and group 2 - people 2 and 3.
Our task is to determine if a feasible group split is possible or not according to these conditions.
To solve the problem, we can use the algorithm for checking whether a graph is bipartite or not. We can use depth-first search (DFS) algorithm and separate people into two different groups using colors (for example, red and green). The algorithm ensures that if person 'A' and person 'B' are in same group then they have same color, and if they are in different groups, they have different colors.
Solution
1 2python 3class Solution: 4 5 def __init__(self): 6 # Initialize all colors as not assigned yet 7 self.COLOR_UNASSIGNED = 0 8 self.COLOR_GREEN = 1 9 self.COLOR_RED = 2 10 11 # Helper function to assign colors and check if all people can be split into two groups 12 def possibleBipartitionHelper(self, personIndex, color): 13 # Assign color to this person 14 self.colors[personIndex] = color 15 16 # For every person who this person dislikes 17 for dislikedPerson in self.dislikes[personIndex]: 18 if self.colors[dislikedPerson] == color: 19 # If the disliked person is already colored with same color, then it cannot be split into two groups 20 return False 21 if self.colors[dislikedPerson] == self.COLOR_UNASSIGNED and not self.possibleBipartitionHelper(dislikedPerson, -color): 22 # If the disliked person is not yet colored then color it with other color and check if split is possible 23 return False 24 25 return True 26 27 28 def possibleBipartition(self, n, dislikes): 29 # self.dislikes[i] is a list of persons that i dislikes 30 self.dislikes = [[] for _ in range(n+1)] 31 32 for p, q in dislikes: 33 self.dislikes[p].append(q) 34 self.dislikes[q].append(p) 35 36 self.colors = [self.COLOR_UNASSIGNED for _ in range(n+1)] 37 38 # Try to color each person 39 for i in range(1, n+1): 40 if self.colors[i] == self.COLOR_UNASSIGNED and not self.possibleBipartitionHelper(i, self.COLOR_GREEN): 41 return False 42 43 return True
This Python solution creates a graph with nodes representing people and edges representing the dislike relationships between people. It then performs depth-first search on the graph and tries to color each node with an opposite color to its parent node. If it cannot do it due to a conflict (two neighbors have the same color), it means it's impossible to divide people into two groups where each person does not dislike anyone from its group, and therefore returns False. If it successfully colors all nodes without conflict, it returns True.# Solution in JavaScript
We can implement the strategy in JavaScript as follows:
1
2javascript
3var possibleBipartition = function(N, dislikes) {
4 let graph = new Array(N+1).fill(0).map(x => []);
5 let group = new Array(N+1);
6 for (let i = 0; i < dislikes.length; i++) {
7 graph[dislikes[i][0]].push(dislikes[i][1]);
8 graph[dislikes[i][1]].push(dislikes[i][0]);
9 };
10
11 for (let i = 1; i <= N; i++) {
12 if (group[i] === undefined && !dfs(i, 0)) {
13 return false;
14 }
15 }
16 return true;
17
18 function dfs(i, g) {
19 if (group[i] !== undefined) {
20 return group[i] === g;
21 }
22 group[i] = g;
23 for (let neighbor of graph[i]) {
24 if (!dfs(neighbor, 1 - g)) {
25 return false;
26 }
27 }
28 return true;
29 };
30};
In the JavaScript implementation above, we create the graph in a similar manner as the Python implementation. The dfs
helper function receives a node index i
and a group g
(0 or 1) and assigns the node to the group g
. Then, it recursively checks each neighbor of the node. If it encounters a neighbor that has already been assigned to the same group or cannot be assigned to the other group, it returns a false value. The main function possibleBipartition
returns true if all nodes can be assigned a group successfully.
Solution in Java
Here's how we can solve the problem in Java:
1
2java
3class Solution {
4 List<Integer>[] graph;
5 Map<Integer, Integer> color;
6
7 public boolean possibleBipartition(int N, int[][] dislikes) {
8 graph = new List[N+1];
9 color = new HashMap<>();
10
11 for (int i = 1; i <= N; ++i)
12 graph[i] = new ArrayList<>();
13
14 for (int[] edge: dislikes) {
15 graph[edge[0]].add(edge[1]);
16 graph[edge[1]].add(edge[0]);
17 }
18
19 for (int node = 1; node <= N; ++node)
20 if (!color.containsKey(node) && !dfs(node, 0))
21 return false;
22 return true;
23 }
24
25 public boolean dfs(int node, int c) {
26 if (color.containsKey(node))
27 return color.get(node) == c;
28 color.put(node, c);
29
30 for (int nei: graph[node])
31 if (!dfs(nei, c ^ 1))
32 return false;
33 return true;
34 }
35}
In the Java implementation, we create a graph using Lists to store the edges and a HashMap to store the color assignments of the nodes. The dfs
function in this version is the same as in the JavaScript version. It uses XOR to alternate between the two groups (0 and 1). If it encounters a neighboring node that has already been assigned to the same group or cannot be assigned to the other group, it returns false. The main function possibleBipartition
returns true if all nodes can be assigned a group successfully.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.