class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {

        int n = (int)graph.size();

        vector<vector<int>>g(n);

        for(int i=0;i<n;i++){
            auto temp = graph[i];

            for(int j:temp){
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }

        vector<int>col(n, -1);
        for(int i=0;i<n;i++){
            if(col[i] == -1){
                if(!dfs(i, 0, g, col)) return false;
            }
        }

        return true;
    }


    bool dfs(int node, int c, vector<vector<int>>&g, vector<int>&col){

        col[node]=c;

        bool res = true;
        for(int child:g[node]){
            if(col[child] == -1){
                res&=dfs(child, 1-c, g, col);
            }
            if(col[child] == c){
                return false;
            }
        }

        return res;
    }
};