深度优先遍历
- 思路：
- 搜索逻辑参见力扣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 statevisited[u] = 1;for (int v : digraph[u]) {// init stateif (visited[v] == 0) {dfs(v);if (!valid) {return;}} else if (visited[v] == 1) {// ringvalid = 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;
};
