# Untitled

unknown
plain_text
3 years ago
3.5 kB
1
Indexable
Never
```https://leetcode.com/problems/possible-bipartition/
class Solution {
public:
void dfs(int root, const vector<vector<int>>& g, vector<int>& color, int currColor) {
color[root] = currColor;
for (int i = 0; i < g[root].size(); i++) {
int child = g[root][i];
if (!color[child]) {
dfs(child, g, color, 3 - currColor);
}
}
}

bool twoColorable(int n, const vector<vector<int>>& g, vector<int>& color) {
for (int i = 1; i <= n; i++) {
if (!color[i]) {
dfs(i, g, color, 1);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < g[i].size(); j++) {
if (color[i] == color[g[i][j]]) {
return false;
}
}
}
return true;
}

bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
vector<vector<int>> g(n + 1);
for (int i = 0; i < dislikes.size(); i++) {
g[dislikes[i][0]].push_back(dislikes[i][1]);
g[dislikes[i][1]].push_back(dislikes[i][0]);
}
vector<int> color(n + 1, 0);
return twoColorable(n, g, color);
}
};

class Solution {
public:
bool dfs(int root, const vector<vector<int>>& g, vector<int>& color, int currColor) {
color[root] = currColor;
bool ok = true;
for (int i = 0; i < g[root].size(); i++) {
int child = g[root][i];
if (color[child] == currColor) {
return false;
} else {
ok &= dfs(child, g, color, 3 - currColor);
}
}
return ok;
}

bool twoColorable(int n, const vector<vector<int>>& g, vector<int>& color) {
for (int i = 1; i <= n; i++) {
if (!color[i]) {
if (!dfs(i, g, color, 1)) {
return false;
}
}
}
return true;
}

bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
vector<vector<int>> g(n + 1);
for (int i = 0; i < dislikes.size(); i++) {
g[dislikes[i][0]].push_back(dislikes[i][1]);
g[dislikes[i][1]].push_back(dislikes[i][0]);
}
vector<int> color(n + 1, 0);
return twoColorable(n, g, color);
}
};

class Solution {
public:
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
vector<vector<int>> g(n + 1);
for (int i = 0; i < dislikes.size(); i++) {
g[dislikes[i][0]].push_back(dislikes[i][1]);
g[dislikes[i][1]].push_back(dislikes[i][0]);
}
vector<int> color(n + 1, 0);
for (int i = 1; i <= n; i++) {
if (!color[i]) {
color[i] = 1;
queue<int> q;
q.push(i);
while(!q.empty()) {
int curr = q.front();
q.pop();
for (int j = 0; j < g[curr].size(); j++) {
if (color[curr] == color[g[curr][j]]) {
return false;
}
if (!color[g[curr][j]]) {
color[g[curr][j]] = 3 - color[curr];
q.push(g[curr][j]);
}
}
}
}
}
return true;
}
};```