leetcode

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

0886.cpp (910B)

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