Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 210. Course Schedule II

---

題目：


解答：

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> ans;
        vector<int> state(numCourses, 0);
        vector<vector<int>> graph(numCourses);

        for (auto& p : prerequisites) {
            graph[p[0]].push_back(p[1]);
        }

        auto dfs = [&](this auto&& dfs, int n) -> bool {
            if (state[n] == 1) {
                return false;
            }

            if (state[n] == 2) {
                return true;
            }

            state[n] = 1;
            for (int v : graph[n]) {
                if (!dfs(v)) {
                    return false;
                }
            }
            state[n] = 2;
            ans.push_back(n);
            return true;
        };

        for (int i = 0; i < numCourses; ++i) {
            if (!dfs(i)) {
                return {};
            }
        }

        return ans;
    }
};