Untitled

    //////////////// DFS APPROACH //////////////////////
public:
    bool isBipartite(vector<vector<int>>& adjList) {
        int n = adjList.size();
        vector<int> color(n, 0); // color = 0 [uncolored], 1 [colored with Red], 2 [colored with blue]

        for (int i = 0; i < n; i++) { // cover all disconnected components
            if (color[i] == 0) {
                if (!dfsColor(i, color, adjList, 2))
                    return false;
            }
        }

        // all components can be colored.
        return true;
    }

    // check if component can be colored with 2 colors
    bool dfsColor(int node, vector<int> &color, vector<vector<int>> &adjList, int parentColor) {
        if (color[node] != 0) // if node already colored
            if (color[node] == parentColor) // if node's color same as parent color -> Not bipartite
                return false;
            else return true;

        // assign opposite color of parent
        color[node] = (parentColor == 1 ? 2 : 1);

        for (auto connNode : adjList[node]) {
            if (!dfsColor(connNode, color, adjList, color[node]))
                // if any of the path return NOT bipartite then return false and don't check any further.
                return false;
        }

        return true;
    }