Leetcode—207. 课程表【中等】

2024每日刷题（145）

Leetcode—207. 课程表

图实现代码

enum class State {
    init, visiting, visited
};

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<State> stat(numCourses);

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

        for(int i = 0; i < numCourses; i++) {
            if(hasCycle(graph, i, stat)) {
                return false;
            }
        }
        return true;
    }
private:
    bool hasCycle(vector<vector<int>>& graph, int u, vector<State>& stat) {
        if(stat[u] == State::visiting) {
            return true;
        }

        if(stat[u] == State::visited) {
            return false;
        }

        stat[u] = State::visiting;
        for(const int v: graph[u]) {
            if(hasCycle(graph, v, stat)) {
                return true;
            }
        }
        stat[u] = State::visited;
        return false;
    }
};

运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！