Untitled

https://leetcode.com/problems/possible-bipartition/
class Solution {
public:
    void dfs(int root, const vector<vector<int>>& g, vector<int>& color, int currColor) {
        color[root] = currColor;
        for (int i = 0; i < g[root].size(); i++) {
            int child = g[root][i];
            if (!color[child]) {
                dfs(child, g, color, 3 - currColor);
            }
        }
    }
    
    bool twoColorable(int n, const vector<vector<int>>& g, vector<int>& color) {
        for (int i = 1; i <= n; i++) {
            if (!color[i]) {
                dfs(i, g, color, 1);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < g[i].size(); j++) {
                if (color[i] == color[g[i][j]]) {
                    return false;
                }
            }
        }
        return true;
    }
    
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<vector<int>> g(n + 1);
        for (int i = 0; i < dislikes.size(); i++) {
            g[dislikes[i][0]].push_back(dislikes[i][1]);
            g[dislikes[i][1]].push_back(dislikes[i][0]);
        }
        vector<int> color(n + 1, 0);
        return twoColorable(n, g, color);
    }
};


class Solution {
public:
    bool dfs(int root, const vector<vector<int>>& g, vector<int>& color, int currColor) {
        color[root] = currColor;
        bool ok = true;
        for (int i = 0; i < g[root].size(); i++) {
            int child = g[root][i];
            if (color[child] == currColor) {
                return false;
            } else {
                ok &= dfs(child, g, color, 3 - currColor);
            }
        }
        return ok;
    }
    
    bool twoColorable(int n, const vector<vector<int>>& g, vector<int>& color) {
        for (int i = 1; i <= n; i++) {
            if (!color[i]) {
                if (!dfs(i, g, color, 1)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<vector<int>> g(n + 1);
        for (int i = 0; i < dislikes.size(); i++) {
            g[dislikes[i][0]].push_back(dislikes[i][1]);
            g[dislikes[i][1]].push_back(dislikes[i][0]);
        }
        vector<int> color(n + 1, 0);
        return twoColorable(n, g, color);
    }
};

class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<vector<int>> g(n + 1);
        for (int i = 0; i < dislikes.size(); i++) {
            g[dislikes[i][0]].push_back(dislikes[i][1]);
            g[dislikes[i][1]].push_back(dislikes[i][0]);
        }
        vector<int> color(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            if (!color[i]) {
                color[i] = 1;
                queue<int> q;
                q.push(i);
                while(!q.empty()) {
                    int curr = q.front();
                    q.pop();
                    for (int j = 0; j < g[curr].size(); j++) {
                        if (color[curr] == color[g[curr][j]]) {
                            return false;
                        } 
                        if (!color[g[curr][j]]) {
                            color[g[curr][j]] = 3 - color[curr];
                            q.push(g[curr][j]);
                        }
                    }
                }
            }
        }
        return true;
    }
};