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.