深度优先遍历
- 思路: - 搜索逻辑参见力扣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 所有, 如有侵权,请联系我们删除。
版权归原作者 slowfastflow 所有, 如有侵权,请联系我们删除。