← all categories

Bipartite Check 0aa26d17

Bipartiteness check via BFS 2-coloring, handles disconnected graphs. Returns {color, ok}; color[i] is 1 or -1 when ok, undefined otherwise.

Time: O(V + E). tested

content/graphs/bipartite-check.h

pair<vector<int>, bool> bipartiteCheck(int n, vector<vector<int>> &adj) {
    vector<int> color(n, 0);
    for (int s = 0; s < n; s++) {
        if (color[s]) continue;
        color[s] = 1;
        queue<int> q; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (!color[v]) { color[v] = -color[u]; q.push(v); }
                else if (color[v] == color[u]) return {{}, false};
            }
        }
    }
    return {color, true};
}