寻找合肥网站建设,做放单主持的网站,网站建设纳千网络,建设网站实验活动小结深度优先遍历
思路#xff1a; 搜索逻辑参见力扣207.课程表需要课程安排的顺序#xff0c;课程搜索完成时#xff0c;将其存储起来即可#xff1b;存储课程的顺序需要注意#xff1a; 输入依赖中 [A, B]图中表示 B - A #xff0c;表示先 B 后 A#x…深度优先遍历
思路 搜索逻辑参见力扣207.课程表需要课程安排的顺序课程搜索完成时将其存储起来即可存储课程的顺序需要注意 输入依赖中 [A, B]图中表示 B - A 表示先 B 后 A可能有其他课程也会依赖 A比如 [C, A]有向图表示 A - C先标记染色的是叶子节点 C而先需要安排的课程是 B所以存储顺序需要反向所以 207 课程表中的思路逻辑描述有误
class Solution {
public:vectorint findOrder(int numCourses, vectorvectorint 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::vectorstd::vectorint digraph;std::vectorint visited;std::vectorint result;bool valid true;
};
