graph_biparate.cpp

vector<vector<ll>> adj;
vector<ll> color;  // 0: no color, 1: color1, 2: color2
ll one = 0, two = 0;
bool isBipartite = true;

bool bfs(ll u)
{
    color[u] = 1;
    one++;
    
    queue<ll> q;
    q.push(u);
    
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        
        for (auto &v : adj[x])
        {
            if (color[v] == 0)
            {
                // Assign alternate color
                color[v] = 3 - color[x];
                if (color[v] == 1)
                    one++;
                else
                    two++;
                q.push(v);
            }
            else if (color[v] == color[x])
            {
                // Same color adjacent nodes - not bipartite
                isBipartite = false;
                return false;
            }
        }
    }
    return true;
}

// Usage for entire graph (handles disconnected components)
void checkBipartite(ll n) {
    color.assign(n, 0);
    isBipartite = true;
    one = 0; two = 0;
    
    for (ll i = 0; i < n; i++) {
        if (color[i] == 0) {
            if (!bfs(i)) {
                cout << "Graph is NOT bipartite!" << endl;
                return;
            }
        }
    }
    
    if (isBipartite) {
        cout << "Graph is bipartite" << endl;
        cout << "Color 1 nodes: " << one << endl;
        cout << "Color 2 nodes: " << two << endl;
    }
}