aboutsummaryrefslogtreecommitdiff
path: root/graph_bipartite.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'graph_bipartite.cpp')
-rw-r--r--graph_bipartite.cpp30
1 files changed, 30 insertions, 0 deletions
diff --git a/graph_bipartite.cpp b/graph_bipartite.cpp
new file mode 100644
index 0000000..b37972d
--- /dev/null
+++ b/graph_bipartite.cpp
@@ -0,0 +1,30 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ vector<int> vis, col;
+ bool isBipartite(vector<vector<int>> &graph) {
+ int n = graph.size();
+ vis.resize(n);
+ col.resize(n);
+ for (int i = 0; i < n; i++)
+ if (vis[i] == 0 && dfs(i, 0, graph) == false)
+ return false;
+ return true;
+ }
+
+private:
+ bool dfs(int v, int c, vector<vector<int>> &graph) {
+ vis[v] = 1;
+ col[v] = c;
+ for (int child : graph[v])
+ if (vis[child] == 0) {
+ if (dfs(child, c ^ 1, graph) == false)
+ return false;
+ } else if (col[v] == col[child])
+ return false;
+ return true;
+ }
+};
+
+int main() {}