Steward

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

程式語言 - LeetCode - C++ - 207. Course Schedule

---

題目：


方法：

用3種狀態：
0 = 未訪問
1 = 訪問中（正在 recursion stack）
2 = 已完成

如果遇到1代表有環

解答：

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        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;
            return true;
        };

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

        return true;
    }
};