886.Possible Bipartition¶
Tags: Medium
Depth-first Search
Links: https://leetcode.com/problems/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 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
- There does not exist
i != j
for whichdislikes[i] == dislikes[j]
.
class Solution {
vector<vector<int>> denseGraph;
vector<int> color;
int n;
public:
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
denseGraph.resize(N + 1, vector<int>(N + 1, 0));
color.resize(N + 1, -1);
n = N;
for (auto & e : dislikes) {
denseGraph[e[0]][e[1]] = 1;
denseGraph[e[1]][e[0]] = 1;
}
bool flag = true;
for (int i = 1; i <= N; ++i) {
if (color[i] == -1) { //第i个点还没有被染色
if (!DFS(i, 0)) { flag = false; break; }
}
}
return flag;
}
bool DFS(int v, int c)
{
color[v] = (c + 1) % 2;
for (int i = 1; i <= n; ++i) {
if (denseGraph[v][i]) {
if (color[i] == -1) {
if (!DFS(i, color[v])) return false;
}
else if (color[i] != c) return false;
}
}
return true;
}
};
二部图染色问题。