210. Course Schedule II

topological sort
bfs O(n)

class Solution {
public:
    struct P { int indeg = 0; vector<int> children; };
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        int n = numCourses;
        vector<P> courses(n);
        unordered_set<int> zero_indeg;
        for (int i = 0; i < n; ++i) zero_indeg.insert(i);
        for (const auto &p : prerequisites) {
            courses[p.second].children.push_back(p.first);
            ++courses[p.first].indeg;
            zero_indeg.erase(p.first);
        }
        vector<int> res;
        while (!zero_indeg.empty()) {
            int c = *zero_indeg.begin();
            res.push_back(c);
            zero_indeg.erase(c);
            for (auto child : courses[c].children) {
                --courses[child].indeg;
                if (courses[child].indeg == 0) {
                    zero_indeg.insert(child);
                }
            }
        }
        if (res.size() < n) return {};
        return res;
    }
};

dfs O(n)

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        n = numCourses;
        visited.resize(n);
        g.resize(n);
        for (const auto &p : prerequisites) {
            g[p[1]].push_back(p[0]);
        }
        for (int i = 0; i < n; ++i) {
            if (dfs(i)) return {};
        }
        return vector<int>(rbegin(s), rend(s));
    }

    bool dfs(int c) {
        if (visited[c] != 0) return visited[c] == -1;
        visited[c] = -1;
        for (auto child : g[c]) {
            if (dfs(child)) return true;
        }
        visited[c] = 1;
        s.push_back(c);
        return false;
    }

    int n;
    vector<int> visited;
    vector<int> s;
    vector<vector<int>> g;
};

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        n = numCourses;
        visited.resize(n);
        g.resize(n);
        for (const auto &p : prerequisites) {
            g[p.second].push_back(p.first);
        }
        for (int i = 0; i < n; ++i) {
            if (dfs(i)) return {}; // true意味着有圈
        }
        vector<int> res;
        while (!s.empty()) {
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }

    bool dfs(int c) {
        if (visited[c] == 1) return false; // 1表示无圈已访问过，0表示未访问，-1表示不知道有没有圈但是已访问过
        if (visited[c] == -1) return true; // -1说明有圈
        visited[c] = -1;
        for (auto child : g[c]) {
            if (dfs(child)) return true;
        }
        visited[c] = 1;
        s.push(c);
        return false;
    }

    int n;
    vector<int> visited;
    stack<int> s;
    vector<vector<int>> g;
};