886. Possible Bipartition

Posted on Edited on In

886. Possible Bipartition

Description

Difficulty: Medium

Related Topics: Depth-First Search, Breadth-First Search, Union Find, Graph

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.

Example 1:

1
2
3
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
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.

Constraints:

  • 1 <= n <= 2000
  • 0 <= dislikes.length <= 104
  • dislikes[i].length == 2
  • 1 <= ai < bi <= n
  • All the pairs of dislikes are unique.

Hints/Nodes

  • Build the map, then it’s find bipartition of the graph
  • Use two vectors: visited and color
  • Use a global boolean ok for fast return

Solution

Language: C++

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    vector<vector<int>> graph;
    vector<bool> visited;
    vector<bool> color;
    int ok = true;

    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        graph = vector<vector<int>>(n + 1, vector<int>());
        visited = vector<bool>(n + 1, false);
        color = vector<bool>(n + 1, false);

        buildGraph(dislikes);

        for (int i = 1; i <= n; i++) {
            traverse(i);
        }

        return ok;
    }

    void buildGraph(vector<vector<int>>& dislikes) {
        for (auto pair : dislikes) {
            int n1 = pair[0];
            int n2 = pair[1];
            graph[n1].push_back(n2);
            graph[n2].push_back(n1);
        }
    }

    void traverse(int node) {
        if (!ok) return;
        visited[node] = true;

        for (int to : graph[node]) {
            if (visited[to]) {
                if (color[to] == color[node]) {
                    ok = false;
                    return;
                }
            } else {
                color[to] = !color[node];
                traverse(to);
            }
        }
    }
};