具体参考 207,一模一样的题目只是最后多了学习课程的输出 ,注意下深搜栈先入后出,最后输出需要reverse一下result
207题解: link
class Solution {
//dfs深度优先
private:
//输入:课程数 课程关系prerequisites
vector<vector<int>> edges;//二维数组
vector<int> visited; //访问情况
vector<int> result;
bool valid = true;
public:
void dfs(int u)
{
visited[u] = 1;
for(int v :edges[u])
{
if(visited[v] == 0)
{
dfs(v);
if(!valid)
{
return;
}
}
else if(visited[v] == 1)
{
valid = false;
return;
}
}
visited[u] = 2;
result.push_back(u);
}
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
edges.resize(numCourses);
visited.resize(numCourses);
for(const auto& info :prerequisites)
{
edges[info[1]].push_back(info[0]);
}
for(int i = 0;i<numCourses &&valid;i++)
{
if(!visited[i])
{
dfs(i);
}
if(!valid)
{
return{
};
}
}
reverse(result.begin(),result.end());
return result;
}
};
文章评论