diff options
Diffstat (limited to 'graph_bipartite.cpp')
-rw-r--r-- | graph_bipartite.cpp | 30 |
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() {} |