Description

Submission

class Solution {
    vector<vector<int>> dislikes2;
    vector<int> color;
    bool dfs(int node) {
        for(auto x: dislikes2[node]) {
            if(color[x] == color[node]) return false;
            if(!color[x]) {
                color[x] = 3 - color[node];
                dfs(x);
            }
        }

        return true;
    }
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        dislikes2.resize(n+1);
        color.resize(n+1, 0);  // 0 for none, 1 for red, 2 for blue

        for(auto& dislike: dislikes) {
            dislikes2[dislike[0]].push_back(dislike[1]);
            dislikes2[dislike[1]].push_back(dislike[0]);
        }

        for(int i = 0; i < n; ++i) {
            if(color[i]) continue;
            color[i] = 1;
            if(!dfs(i)) return false;
        }

        return true;
    }
};