leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0886.cpp (910B)

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