Possible Bipartition
Possible Bipartition is a medium graphs problem solved with the cycle detection pattern.
The best approach, optimal (bfs two-coloring), runs in O(n + m) time and O(n + m) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from union-find (merge the enemies of each person) up.
Problem
There are n people, numbered from 1 to n, and you want to split them into two groups (either group may be any size, including empty).
You are given a list dislikes, where dislikes[i] = [a, b] means person a and person b must not be in the same group. Return true if a split that respects every dislike exists, and false otherwise.
Examples
Example 1
- Input
n = 5, dislikes = [[1, 2], [2, 3], [4, 5]]- Output
true- Why
- Put {1, 3, 4} in one group and {2, 5} in the other.
Example 2
- Input
n = 4, dislikes = [[1, 2], [2, 4], [1, 4]]- Output
false- Why
- 1, 2 and 4 all dislike each other; three people in a cycle cannot be split into two groups.
Example 3
- Input
n = 3, dislikes = []- Output
true- Why
- Nobody dislikes anybody, so any split works.
Constraints
1 <= n <= 20000 <= dislikes.length <= 10^4dislikes[i].length == 2,1 <= a_i < b_i <= n- All pairs in
dislikesare distinct
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Union-find (merge the enemies of each person) | O((n + m) · α(n)) | O(n + m) |
| Optimal (BFS two-coloring) | O(n + m) | O(n + m) |
1Union-find (merge the enemies of each person)
O((n + m) · α(n))Each edge is touched a constant number of times; union-find operations are nearly constant with path compression.O(n + m)Adjacency lists and the parent array.All the people that one person dislikes must end up in the same group as each other (the group opposite to that person). Union them together with union-find, then check that no person is in the same set as someone they dislike.
- Build adjacency lists from the dislikes.
- For each person u, union all of u's neighbours with the first neighbour.
- For each person u and each neighbour v, if find(u) == find(v), return false.
- Return true.
class Solution {
private int[] parent;
public boolean possibleBipartition(int n, int[][] dislikes) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int[] d : dislikes) {
adj.get(d[0]).add(d[1]);
adj.get(d[1]).add(d[0]);
}
parent = new int[n + 1];
for (int i = 0; i <= n; i++) parent[i] = i;
for (int u = 1; u <= n; u++) {
List<Integer> nb = adj.get(u);
for (int k = 1; k < nb.size(); k++) union(nb.get(0), nb.get(k));
}
for (int u = 1; u <= n; u++) {
for (int v : adj.get(u)) {
if (find(u) == find(v)) return false;
}
}
return true;
}
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
private void union(int a, int b) {
parent[find(a)] = find(b);
}
}class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
adj = [[] for _ in range(n + 1)]
for a, b in dislikes:
adj[a].append(b)
adj[b].append(a)
parent = list(range(n + 1))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u in range(1, n + 1):
nb = adj[u]
for k in range(1, len(nb)):
parent[find(nb[0])] = find(nb[k])
for u in range(1, n + 1):
for v in adj[u]:
if find(u) == find(v):
return False
return Trueclass Solution {
public:
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
vector<vector<int>> adj(n + 1);
for (auto& d : dislikes) {
adj[d[0]].push_back(d[1]);
adj[d[1]].push_back(d[0]);
}
parent.assign(n + 1, 0);
for (int i = 0; i <= n; i++) parent[i] = i;
for (int u = 1; u <= n; u++) {
for (size_t k = 1; k < adj[u].size(); k++) parent[find(adj[u][0])] = find(adj[u][k]);
}
for (int u = 1; u <= n; u++) {
for (int v : adj[u]) {
if (find(u) == find(v)) return false;
}
}
return true;
}
private:
vector<int> parent;
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
};function possibleBipartition(n, dislikes) {
const adj = Array.from({ length: n + 1 }, () => []);
for (const [a, b] of dislikes) {
adj[a].push(b);
adj[b].push(a);
}
const parent = Array.from({ length: n + 1 }, (_, i) => i);
const find = (x) => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
for (let u = 1; u <= n; u++) {
for (let k = 1; k < adj[u].length; k++) parent[find(adj[u][0])] = find(adj[u][k]);
}
for (let u = 1; u <= n; u++) {
for (const v of adj[u]) {
if (find(u) === find(v)) return false;
}
}
return true;
}2Optimal (BFS two-coloring)
O(n + m)Every person is enqueued once and every dislike is examined twice (once from each end).O(n + m)Adjacency lists, the color array and the queue.Treat people as nodes and dislikes as edges. Visit every component with BFS, giving the start color 0 and every newly reached neighbour the opposite color of the node it came from. If an edge ever connects two nodes of the same color, the component has an odd cycle and the split is impossible.
- Build adjacency lists; color[] = -1 for everyone.
- For each uncolored person s: color[s] = 0 and BFS from s.
- For each edge (u, v) seen: if v is uncolored, color[v] = 1 - color[u] and enqueue v; if color[v] == color[u], return false.
- Return true when every component is colored.
class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int[] d : dislikes) {
adj.get(d[0]).add(d[1]);
adj.get(d[1]).add(d[0]);
}
int[] color = new int[n + 1];
Arrays.fill(color, -1);
Deque<Integer> queue = new ArrayDeque<>();
for (int s = 1; s <= n; s++) {
if (color[s] != -1) continue;
color[s] = 0;
queue.add(s);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : adj.get(u)) {
if (color[v] == -1) {
color[v] = 1 - color[u];
queue.add(v);
} else if (color[v] == color[u]) {
return false;
}
}
}
}
return true;
}
}class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
adj = [[] for _ in range(n + 1)]
for a, b in dislikes:
adj[a].append(b)
adj[b].append(a)
color = [-1] * (n + 1)
for s in range(1, n + 1):
if color[s] != -1:
continue
color[s] = 0
queue = deque([s])
while queue:
u = queue.popleft()
for v in adj[u]:
if color[v] == -1:
color[v] = 1 - color[u]
queue.append(v)
elif color[v] == color[u]:
return False
return Trueclass Solution {
public:
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
vector<vector<int>> adj(n + 1);
for (auto& d : dislikes) {
adj[d[0]].push_back(d[1]);
adj[d[1]].push_back(d[0]);
}
vector<int> color(n + 1, -1);
for (int s = 1; s <= n; s++) {
if (color[s] != -1) continue;
color[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (color[v] == -1) {
color[v] = 1 - color[u];
q.push(v);
} else if (color[v] == color[u]) {
return false;
}
}
}
}
return true;
}
};function possibleBipartition(n, dislikes) {
const adj = Array.from({ length: n + 1 }, () => []);
for (const [a, b] of dislikes) {
adj[a].push(b);
adj[b].push(a);
}
const color = new Array(n + 1).fill(-1);
for (let s = 1; s <= n; s++) {
if (color[s] !== -1) continue;
color[s] = 0;
const queue = [s];
let head = 0;
while (head < queue.length) {
const u = queue[head++];
for (const v of adj[u]) {
if (color[v] === -1) {
color[v] = 1 - color[u];
queue.push(v);
} else if (color[v] === color[u]) {
return false;
}
}
}
}
return true;
}Edge cases to test
- No dislikes at all
- A single person
- Several disconnected groups of people, only one of which contains an odd cycle
- A long even cycle (fine) versus a long odd cycle (impossible)
Hints
Hint 1
Draw a graph: people are nodes and every dislike is an edge. Each edge must go between the two groups.
Hint 2
That is exactly the question 'is this graph bipartite?', i.e. does it have no odd cycle?
Hint 3
Color each component with BFS: a neighbour gets the opposite color, and a neighbour that already has the same color proves it is impossible.
FAQ
What is the best time complexity for Possible Bipartition?
Optimal (BFS two-coloring) runs in O(n + m) time and O(n + m) extra space. Every person is enqueued once and every dislike is examined twice (once from each end).
Which pattern does Possible Bipartition use?
It is a graphs problem that uses the cycle detection pattern. Other problems with the same pattern: Undirected Graph Cycle, Directed Graph Cycle, Is Graph Bipartite?.
Is there a brute force solution for Possible Bipartition?
Yes. Union-find (merge the enemies of each person) takes O((n + m) · α(n)) time and O(n + m) space. All the people that one person dislikes must end up in the same group as each other (the group opposite to that person).
Which edge cases should I test for Possible Bipartition?
No dislikes at all; A single person; Several disconnected groups of people, only one of which contains an odd cycle; A long even cycle (fine) versus a long odd cycle (impossible).