力扣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;
};