Untitled
unknown
plain_text
4 years ago
3.5 kB
6
Indexable
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; } };
Editor is loading...