Possible Bipartition
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.
Examples
Example 1:
Input:
n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output:
true
Explanation: The first group has [1,4], and the second group has [2,3].
Example 2:
Input:
n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output:
false
Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.
Solution
Method 1 – Graph Coloring (DFS/Union-Find)
Intuition
The key idea is to check if the graph is bipartite: can we color the graph with two colors such that no two adjacent nodes have the same color? If yes, a bipartition is possible. This can be done using DFS coloring or Union-Find by grouping each node with the opposite group of its neighbors.
Approach
- Build the adjacency list for the graph (1-based to 0-based).
- Initialize a color array with -1 (uncolored).
- For each uncolored node, start DFS and try to color it and its neighbors with alternate colors.
- If a conflict is found (neighbor has the same color), return false.
- If all nodes can be colored, return true.
Code
C++
class Solution {
public:
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
vector<vector<int>> g(n);
for (auto& e : dislikes) {
g[e[0]-1].push_back(e[1]-1);
g[e[1]-1].push_back(e[0]-1);
}
vector<int> color(n, -1);
function<bool(int, int)> dfs = [&](int u, int c) {
color[u] = c;
for (int v : g[u]) {
if (color[v] == -1) {
if (!dfs(v, 1-c)) return false;
} else if (color[v] == c) {
return false;
}
}
return true;
};
for (int i = 0; i < n; ++i) if (color[i] == -1 && !dfs(i, 0)) return false;
return true;
}
};
Go
func possibleBipartition(n int, dislikes [][]int) bool {
g := make([][]int, n)
for _, e := range dislikes {
g[e[0]-1] = append(g[e[0]-1], e[1]-1)
g[e[1]-1] = append(g[e[1]-1], e[0]-1)
}
color := make([]int, n)
for i := range color { color[i] = -1 }
var dfs func(int, int) bool
dfs = func(u, c int) bool {
color[u] = c
for _, v := range g[u] {
if color[v] == -1 {
if !dfs(v, 1-c) { return false }
} else if color[v] == c {
return false
}
}
return true
}
for i := 0; i < n; i++ {
if color[i] == -1 && !dfs(i, 0) {
return false
}
}
return true
}
Java
class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
List<Integer>[] g = new List[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int[] e : dislikes) {
g[e[0]-1].add(e[1]-1);
g[e[1]-1].add(e[0]-1);
}
int[] color = new int[n];
Arrays.fill(color, -1);
for (int i = 0; i < n; i++) {
if (color[i] == -1 && !dfs(i, 0, color, g)) return false;
}
return true;
}
private boolean dfs(int u, int c, int[] color, List<Integer>[] g) {
color[u] = c;
for (int v : g[u]) {
if (color[v] == -1) {
if (!dfs(v, 1-c, color, g)) return false;
} else if (color[v] == c) {
return false;
}
}
return true;
}
}
Kotlin
class Solution {
fun possibleBipartition(n: Int, dislikes: Array<IntArray>): Boolean {
val g = Array(n) { mutableListOf<Int>() }
for (e in dislikes) {
g[e[0]-1].add(e[1]-1)
g[e[1]-1].add(e[0]-1)
}
val color = IntArray(n) { -1 }
fun dfs(u: Int, c: Int): Boolean {
color[u] = c
for (v in g[u]) {
if (color[v] == -1) {
if (!dfs(v, 1-c)) return false
} else if (color[v] == c) {
return false
}
}
return true
}
for (i in 0 until n) if (color[i] == -1 && !dfs(i, 0)) return false
return true
}
}
Python
class Solution:
def possibleBipartition(self, n: int, dislikes: list[list[int]]) -> bool:
g = [[] for _ in range(n)]
for u, v in dislikes:
g[u-1].append(v-1)
g[v-1].append(u-1)
color = [-1] * n
def dfs(u: int, c: int) -> bool:
color[u] = c
for v in g[u]:
if color[v] == -1:
if not dfs(v, 1-c):
return False
elif color[v] == c:
return False
return True
for i in range(n):
if color[i] == -1 and not dfs(i, 0):
return False
return True
Rust
impl Solution {
pub fn possible_bipartition(n: i32, dislikes: Vec<Vec<i32>>) -> bool {
let n = n as usize;
let mut g = vec![vec![]; n];
for e in &dislikes {
g[(e[0]-1) as usize].push((e[1]-1) as usize);
g[(e[1]-1) as usize].push((e[0]-1) as usize);
}
let mut color = vec![-1; n];
fn dfs(u: usize, c: i32, color: &mut Vec<i32>, g: &Vec<Vec<usize>>) -> bool {
color[u] = c;
for &v in &g[u] {
if color[v] == -1 {
if !dfs(v, 1-c, color, g) { return false; }
} else if color[v] == c {
return false;
}
}
true
}
for i in 0..n {
if color[i] == -1 && !dfs(i, 0, &mut color, &g) {
return false;
}
}
true
}
}
TypeScript
class Solution {
possibleBipartition(n: number, dislikes: number[][]): boolean {
const g: number[][] = Array.from({length: n}, () => []);
for (const [u, v] of dislikes) {
g[u-1].push(v-1);
g[v-1].push(u-1);
}
const color = Array(n).fill(-1);
const dfs = (u: number, c: number): boolean => {
color[u] = c;
for (const v of g[u]) {
if (color[v] === -1) {
if (!dfs(v, 1-c)) return false;
} else if (color[v] === c) {
return false;
}
}
return true;
};
for (let i = 0; i < n; i++) if (color[i] === -1 && !dfs(i, 0)) return false;
return true;
}
}
Complexity
- ⏰ Time complexity:
O(n + m), where n is the number of people and m is the number of dislikes; each node and edge is visited once. - 🧺 Space complexity:
O(n + m), for the adjacency list and color array.