# Possible Bipartition LeetCode Solution

Difficulty Level Medium
tiktokViews 25

## Problem Statement

Possible Bipartition LeetCode Solution – 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] = [a`i`, b`i`]` indicates that the person labeled `a`i does not like the person labeled `b`i, return `true` if it is possible to split everyone into two groups in this way.

```Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4] and group2 [2,3].```

## Explanation

The question asks us to divide given people into two groups such that no two people in the same group dislike each other.

For ease of understanding, we can represent this problem as a graph, with people being the vertices and dislike-pairs being the edges of this graph.

We have to find out if the vertices can be divided into two sets such that there aren’t any edges between vertices of the same set. A graph satisfying this condition is called a bipartite graph.

We try to color the two sets of vertices, with RED and BLUE colors. In a bipartite graph, a RED vertex must be connected only with BLUE vertices and a BLUE vertex must be connected only with RED vertices. In other words, there must NOT be an edge connecting two vertices of the same color. Such an edge will be a conflict edge.

The presence of conflict edges indicates that bipartition is NOT possible.

The graph may consist of many connected components. For each connected component, we run our BFS algorithm to find conflict edges, if any. For each component, we start by coloring one vertex RED, and all its neighbors BLUE. Then we visit the BLUE vertices and color all their neighbors as RED, and so on. During this process, if we come across any RED-RED edge or BLUE-BLUE edge, we have found a conflict edge and we immediately return false, as bipartition will not be possible.

If no conflict edges are found at the end of the algorithm, it means bipartition is possible, hence we return true. ## Code

### C++ Code For Possible Bipartition

```#define WHITE 0
#define RED 1
#define BLUE 2
class Solution {
public:
bool possibleBipartition(int N, vector<vector<int>> &edges)
{
vector<int> color(N + 1, WHITE);
vector<bool> explored(N + 1, false);
for (auto &edge: edges)
{
int u = edge;
int v = edge;
}

queue<int> q;

for (int i = 1; i <= N; ++i)
{
if (!explored[i])
{
color[i] = RED;
q.push(i);

// perform BFS from vertex i
while (!q.empty())
{
int u = q.front();
q.pop();

// check if u is already explored
if (explored[u])
{
continue;
}

explored[u] = true;

// for each neighbor of u, execute this loop
{
if (color[v] == color[u])
{
return false;
}

// we color v with the opposite color of u
if (color[u] == RED)
{
color[v] = BLUE;
}
else
{
color[v] = RED;
}

q.push(v);
}
}
}
}
return true;
}
};```

### Python Code for Possible Bipartition

```class Solution:
def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
self.graph = collections.defaultdict(list)
group_mapping = {}
for (u, v) in dislikes:                   # Create graph
self.graph[u].append(v)
self.graph[v].append(u)

visited = set()
for i in range(1, N + 1):                 # Iterate each node
if i in visited: continue             # No need to revisit, since it's a non-directed graph
stack = [(i, 0)]                      # Use stack for BFS
while stack:                          # You can also use a deque instead of 2 while loop on stack
tmp_stack = []
while stack:                      # exhaust current stack before go to next layer (BFS)
cur_node, group = stack.pop()
if cur_node in group_mapping and group != group_mapping[cur_node]:  # check if it's conflict
return False
if cur_node in visited: continue        # If visited and no conflict, continue to avoid dead loop
group_mapping[cur_node] = group         # Assign group for current node
for child in self.graph[cur_node]:      # Assign contrary group for dislikes of current node
tmp_stack.append((child, not group))
stack = tmp_stack
return True
```

### Java Code For Possible Bipartiton

```class Solution {
public boolean possibleBipartition(int N, int[][] dislikes) {
int[] color = new int[N + 1];
List<List<Integer>> adj = new ArrayList<>(N + 1);
for(int[] d : dislikes) {
}

for(int i = 1; i <= N; i++) {
if(color[i] == 0) {
color[i] = 1;
while(!q.isEmpty()) {
int cur = q.poll();
if(color[nb] == 0) {
color[nb] = color[cur] == 1 ? 2 : 1;
} else {
if(color[nb] == color[cur]) return false;
}
}
}
}
}
return true;
}
}```

## Complexity Analysis for Possible Bipartition LeetCode Solution

### Time Complexity

O (N + E) since we take O(E) time to create an adjacency list and O (N) time to make a BFS traversal on it.

### Space Complexity

O(N+E) since we store an adjacency list for the graph and also a visited array.

Translate »