Cycle detection / feasibility (Topological Sort Sub-pattern)

// Directed cycle check with three colours: 0 = not seen, 1 = on the current path, 2 = finished.
bool dfsCycle(int u, const vector<vector<int>>& adj, vector<int>& color) {
    color[u] = 1;
    for (int v : adj[u]) {
        if (color[v] == 1) return true;           // back edge to the current path: a cycle
        if (color[v] == 0 && dfsCycle(v, adj, color)) return true;
    }
    color[u] = 2;                                 // every path from u is cycle-free
    return false;
}

bool hasCycle(int n, const vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (auto& e : edges) adj[e[0]].push_back(e[1]);
    vector<int> color(n, 0);
    for (int u = 0; u < n; u++)
        if (color[u] == 0 && dfsCycle(u, adj, color)) return true;
    return false;
}