leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0785.cpp (701B)

      1 class Solution {
      2   public:
      3     bool isBipartite(vector<vector<int>> &graph) {
      4         int n = graph.size();
      5         vector<int> color(n, 0);
      6 
      7         for (int i = 0; i < n; i++) {
      8             if (color[i]) continue;
      9             stack<int> st;
     10             st.push(i), color[i] = 1;
     11             while (!st.empty()) {
     12                 int root = st.top();
     13                 st.pop();
     14                 for (int c : graph[root]) {
     15                     if (color[root] == color[c]) return false;
     16                     if (!color[c]) {
     17                         st.push(c);
     18                         color[c] = -color[root];
     19                     }
     20                 }
     21             }
     22         }
     23         return true;
     24     }
     25 };