Cycle Detection & Topo Sort

class Solution {
private:
    // 有向图
    vector<vector<int>> edges;
    vector<int> visited;
    vector<int> onPath;
    // 拓扑排序
    vector<int> result;
    // 判断是否可以拓扑排序
    bool valid = true;

public:
    void explore(int u) {
        visited[u] = 1;
        onPath[u] = 1;
        for (int v: edges[u]) {
            if (onPath[v]) {
                valid = false;
                return;
            }
            if (!visited[v]) {
                explore(v);
                if (!valid) {
                    return;
                }
            }
        }

        result.push_back(u);  // Post order.
        onPath[u] = 0;
    }

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        onPath.resize(numCourses, 0);
        visited.resize(numCourses, 0);
        for (const auto& info: prerequisites) {
            edges[info[1]].push_back(info[0]);
        }

        for (int i = 0; i < numCourses && valid; ++i) {
            if (!visited[i]) {
                explore(i);
            }
        }
        if (!valid) {
            return {};
        }

        reverse(result.begin(), result.end());
        return result;
    }
};