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 {
public:
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
vector<vector<int>> g(N + , vector<int>(N + ));
for (auto dislike : dislikes) {
g[dislike[]][dislike[]] = ;
g[dislike[]][dislike[]] = ;
}
vector<int> colors(N + );
for (int i = ; i <= N; ++i) {
if (colors[i] == && !helper(g, i, , colors)) return false;
}
return true;
}
bool helper(vector<vector<int>>& g, int cur, int color, vector<int>& colors) {
colors[cur] = color;
for (int i = ; i < g.size(); ++i) {
if (g[cur][i] == ) {
if (colors[i] == color) return false;
if (colors[i] == && !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 + );
for (auto dislike : dislikes) {
g[dislike[]].push_back(dislike[]);
g[dislike[]].push_back(dislike[]);
}
vector<int> colors(N + );
for (int i = ; i <= N; ++i) {
if (colors[i] != ) continue;
colors[i] = ;
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] == ) {
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[]].push_back(dislike[]);
g[dislike[]].push_back(dislike[]);
}
vector<int> root(N + );
for (int i = ; i <= N; ++i) root[i] = i;
for (int i = ; i <= N; ++i) {
if (!g.count(i)) continue;
int x = find(root, i), y = find(root, g[i][]);
if (x == y) return false;
for (int j = ; 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://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