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:

1
2
3
4
5

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:

1
2
3
4
5

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

  1. Build the adjacency list for the graph (1-based to 0-based).
  2. Initialize a color array with -1 (uncolored).
  3. For each uncolored node, start DFS and try to color it and its neighbors with alternate colors.
  4. If a conflict is found (neighbor has the same color), return false.
  5. If all nodes can be colored, return true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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.