0


力扣210. 课程表 II

深度优先遍历

  • 思路: - 搜索逻辑参见​​​​​​力扣207.课程表- 需要课程安排的顺序,课程搜索完成时,将其存储起来即可;- 存储课程的顺序需要注意: - 输入依赖中 [A, B]- 图中表示 B -> A ,表示先 B 后 A;- 可能有其他课程也会依赖 A,比如 [C, A],有向图表示 A -> C;- 先标记染色的是叶子节点 C,而先需要安排的课程是 B;- 所以存储顺序需要反向;(所以 207 课程表中的思路逻辑描述有误)
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        digraph.resize(numCourses);
        visited.resize(numCourses);

        for (const auto & info : prerequisites) {
            digraph[info[1]].push_back(info[0]);
        }

        for (int i = 0; i < numCourses && valid; ++i) {
            if (visited[i] == 0) {
                dfs(i);
            }
        }

        if (!valid) {
            return {};
        }

        std::reverse(result.begin(), result.end());

        return result;
    }

private:
    void dfs(int u) {
        // to search state
        visited[u] = 1;

        for (int v : digraph[u]) {
            // init state
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) {
                    return;
                }
            } else if (visited[v] == 1) {
                // ring
                valid = false;
                return;
            }
        }

        visited[u] = 2;

        result.push_back(u);
    }

private:
    std::vector<std::vector<int>> digraph;
    std::vector<int> visited;
    std::vector<int> result;

    bool valid = true;
};

本文转载自: https://blog.csdn.net/N_BenBird/article/details/135577029
版权归原作者 slowfastflow 所有, 如有侵权,请联系我们删除。

“力扣210. 课程表 II”的评论:

还没有评论