Medium
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 Constraints: 1 <= N <= 2000 0 <= dislikes.length <= 10000 dislikes[i].length == 2 1 <= dislikes[i][j] <= N dislikes[i][0] < dislikes[i][1] There does not exist i != j for which dislikes[i] == dislikes[j].
/*
Method 2: using DFS
the main idea is use dfs to find if a bipartition is possible or not
1. build a graph from the given dislike set
2. usding dfs to assign different colors (blue, red) to the people disliking each other
3. assign fails if dfs encountered a previous node that has been assigned to a same color already
4. succeed if dfs was able to assign colors to all nodes
T(n) = O(E+V)
*/
class Solution {
public:
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
//build a graph
unordered_map<int, unordered_set<int>> G;
for(auto & it : dislikes){
int u = it[0];
int v = it[1];
G[u].insert(v);
G[v].insert(u);
}
//use dfs to assign color: "red", "blue"
unordered_map<int,bool> visited;
for(int i = 1; i <= N; i++){
if(!visited.count(i)){
if(!dfs(G,visited, N, true, i)){
return false;
}
}
}
return true;
}
private:
bool dfs(unordered_map<int, unordered_set<int>>& G, unordered_map<int, bool>& visited, int N, bool color, int u){
visited[u] = color;
if(visited.size() == N){
//do nothing, bca we need to try all reachable to nodes to determine if a bipartition is possible or not
}else{
if(G.count(u)){
bool u_color = visited.at(u);
for(auto v : G.at(u)){
if(!visited.count(v)){
dfs(G, visited, N, !u_color, v);
}
else{
if(u_color == visited.at(v)){
return false;
}
}
}
}
}
//return true if all reachable edges are tried and no adjcent nodes with same color exsit
return true;
}
};/*
Method 1: using BFS
the idea is to use bfs to find if a bipartition is possible or not
1. build a graph from the given dislike set
2. using bfs to assign different colors (blue, red) to the people disliking each other
3. assign fails if dfs encountered a previous node that has been assigned to a same color already
4. succeed if bfs was able to assign colors to all nodes
T(n) = O(E + V)
*/
class Solution {
public:
bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
//build a graph
unordered_map<int, unordered_set<int>> G;
for (auto& it : dislikes) {
int u = it[0];
int v = it[1];
G[u].insert(v);
G[v].insert(u);
}
//use bfs to assign color: "red", "blue"
unordered_map<int, bool> visited;
//bfs, need to look at all node, otherwise it will not pass case
//5, [[1,2],[3,4],[4,5],[3,5]]
for (int i = 1; i <= N; i++) {
if(!visited.count(i)){
queue<int> myQ;
myQ.push(i);
visited[i] = true;
while (!myQ.empty()) {
int u = myQ.front();
myQ.pop();
if (G.count(u)) {
for (auto& v : G.at(u)) {
if (!visited.count(v)) {
visited[v] = !visited.at(u);
myQ.push(v);
}
else {
if (visited.at(u) == visited.at(v)) {
return false;
}
}
}
}
}
}
}
return true;
}
};