# 886. Possible Bipartition

Given a set of `N` people (numbered `1, 2, ..., N`), we would like to split everyone into two groups of any size.

Each person may dislike some other people, and they should not go into the same group.

Formally, if `dislikes[i] = [a, b]`, it means it is not allowed to put the people numbered `a` and `b` into the same group.

Return `true` if and only if it is possible to split everyone into two groups in this way.

Example 1:

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

Example 2:

``````Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
``````

Example 3:

``````Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false
``````

Note:

1. `1 <= N <= 2000`
2. `0 <= dislikes.length <= 10000`
3. `1 <= dislikes[i][j] <= N`
4. `dislikes[i][0] < dislikes[i][1]`
5. There does not exist `i != j` for which `dislikes[i] == dislikes[j]`.

``````class Solution {
public:
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
vector<vector<int>> g(N + 1, vector<int>(N + 1));
for (auto dislike : dislikes) {
g[dislike[0]][dislike[1]] = 1;
g[dislike[1]][dislike[0]] = 1;
}
vector<int> colors(N + 1);
for (int i = 1; i <= N; ++i) {
if (colors[i] == 0 && !helper(g, i, 1, colors)) return false;
}
return true;
}
bool helper(vector<vector<int>>& g, int cur, int color, vector<int>& colors) {
colors[cur] = color;
for (int i = 0; i < g.size(); ++i) {
if (g[cur][i] == 1) {
if (colors[i] == color) return false;
if (colors[i] == 0 && !helper(g, i, -color, colors)) return false;
}
}
return true;
}
};
``````

``````class Solution {
public:
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
vector<vector<int>> g(N + 1);
for (auto dislike : dislikes) {
g[dislike[0]].push_back(dislike[1]);
g[dislike[1]].push_back(dislike[0]);
}
vector<int> colors(N + 1);
for (int i = 1; i <= N; ++i) {
if (colors[i] != 0) continue;
colors[i] = 1;
queue<int> q{{i}};
while (!q.empty()) {
int t = q.front(); q.pop();
for (int cur : g[t]) {
if (colors[cur] == colors[t]) return false;
if (colors[cur] == 0) {
colors[cur] = -colors[t];
q.push(cur);
}
}
}
}
return true;
}
};
``````

``````class Solution {
public:
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
unordered_map<int, vector<int>> g;
for (auto dislike : dislikes) {
g[dislike[0]].push_back(dislike[1]);
g[dislike[1]].push_back(dislike[0]);
}
vector<int> root(N + 1);
for (int i = 1; i <= N; ++i) root[i] = i;
for (int i = 1; i <= N; ++i) {
if (!g.count(i)) continue;
int x = find(root, i), y = find(root, g[i][0]);
if (x == y) return false;
for (int j = 1; j < g[i].size(); ++j) {
int parent = find(root, g[i][j]);
if (x == parent) return false;
root[parent] = y;
}
}
return true;
}
int find(vector<int>& root, int i) {
return root[i] == i ? i : find(root, root[i]);
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/886

Is Graph Bipartite?

https://leetcode.com/problems/possible-bipartition/

https://leetcode.com/problems/possible-bipartition/discuss/159085/java-graph

https://leetcode.com/problems/possible-bipartition/discuss/195303/Java-Union-Find

https://leetcode.com/problems/possible-bipartition/discuss/158957/Java-DFS-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation