Bipartite / two-colouring (Graph BFS / DFS Sub-pattern)

// Two-colouring: give a node colour 0, its neighbours colour 1, and so on; a same-colour edge = not bipartite.
bool isBipartite(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> color(n, -1);
    for (int s = 0; s < n; s++) {                // every component, not just node 0
        if (color[s] != -1) continue;
        color[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (color[v] == -1) { color[v] = 1 - color[u]; q.push(v); }
                else if (color[v] == color[u]) return false;   // an odd cycle
            }
        }
    }
    return true;
}