Leetcode—210. 课程表 II【中等】

2024每日刷题（145）

Leetcode—210. 课程表 II

dfs实现代码

enum class State {
    init, visiting, visited
};

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> ans;
        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, ans)) {
                return {};
            }
        }
        std::reverse(ans.begin(), ans.end());
        return ans;
    }

private:
    bool hasCycle(vector<vector<int>> &graph, int u, vector<State>& stat, vector<int>& ans) {
        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, ans)) {
                return true;
            }
        }
        stat[u] = State::visited;
        ans.push_back(u);
        return false;
    }
};

运行结果

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