class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> ret;
vector<vector<int>> dependency(numCourses, vector<int>());
for (const auto& p : prerequisites){
int left = p[0];
int right = p[1];
dependency[left].push_back(right);
}
deque<int> stack;
for (int i=0; i<numCourses; ++i){
if (find(ret.begin(), ret.end(), i) == ret.end()){
// cout << i << endl;
stack.push_back(i);
if (!dfs(i, dependency, ret, stack)) {
// cout << "loop" << endl;
return {};
}
}
}
return ret;
}
bool dfs(int node, vector<vector<int>>& dependency, vector<int>& ret, deque<int>& stack){
for (const auto& next : dependency[node]){
if (find(stack.begin(), stack.end(), next) != stack.end()){
return false;
}
if (find(ret.begin(), ret.end(), next) == ret.end()){
// cout << next << endl;
stack.push_back(next);
if (!dfs(next, dependency, ret, stack)){
return false;
}
}
}
stack.pop_back();
ret.push_back(node);
return true;
}
};
Runtime: 124 ms, faster than 6.09% of C++ online submissions for Course Schedule II.
Memory Usage: 15.5 MB, less than 6.06% of C++ online submissions for Course Schedule II.
不知道为什么这么慢。
在看别人答案之前，整理下这里面出现的大小问题。
1，得想到这是topological sort，用search （BFS怎么用？）
2，vector的find写起来繁琐。std::find(ret.begin(), ret.end(), i) == ret.end()
3，得判断cycle，而且不只是最外面的for loop要判断，dfs函数里面的也要
4，stack这个变量的用deque，否则没法用find，stack本身，deque的find类似vector
5，把stack（deque）改成searched（unordered set），运行时间到100ms，faster than 9.39%了
6，stack和searched要在dfs结束的时候清除当前元素，否则会误报cycle
其他人的答案：
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
vector<int> ans;
vector<int> indegre(numCourses);
vector<int> visited(numCourses,0);
for(int i=0;i<prerequisites.size();i++){
indegre[prerequisites[i][0]]++;
adj[prerequisites[i][1]].push_back(prerequisites[i][0]);
}
queue<int>q;
for(int i=0;i<numCourses;i++){
if(indegre[i]==0)
q.push(i);
}
while(!q.empty()){
int cur=q.front();
ans.push_back(q.front());
q.pop();
visited[cur]=1;
for(int i=0;i<adj[cur].size();i++){
indegre[adj[cur][i]]--;
if(indegre[adj[cur][i]]==0)
q.push(adj[cur][i]);
}
}
//to check cycle
for(int i=0;i<visited.size();i++){
if(visited[i]==0)
{
ans.clear();
}
}
return ans;
}
};
class Solution {
public:
bool dfs(int node, vector<vector<int>>& graph, vector<int>& visited, vector<int>& result)
{
visited[node]=1;
for(int i=0;i<graph[node].size();i++)
{
if(visited[graph[node][i]]==1)return false; // if this node is unexplored that means there is a cycle
if(visited[graph[node][i]]==0)
{
if(!dfs(graph[node][i],graph,visited,result)) //return false
return false;
}
}
visited[node]=2; //if function comes till here then we can mark the current node as 2 i.e, visited
result.push_back(node); //we will push the visited nodes to the resulting array
return true;
}
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
for(int i=0;i<prerequisites.size();i++)
{
graph[prerequisites[i][0]].push_back(prerequisites[i][1]); //making an adjacency list
}
vector<int> visited(numCourses,0); //for keeping track of the nodes position.
//We first initialize every node as 0 i,e. unvisited
vector<int> result; //result vector
bool flag = true;
for(int i=0;i<numCourses;i++)
{
if(visited[i]==0)
{
if(!dfs(i,graph,visited,result)){
flag = false; // it will return false if there is a cycle detected so we can break it
break;
}
}
}
if(!flag)
return vector<int>();
return result;
}
};
重大改进：（100ms -> 36ms）
1，把node状态的存储变成只有一个固定长度（numCourses）的vector，0表示没搜索过，1表示正在当前搜索，2表示完成搜索过了，这样每次check都是O(1)而且花销很小
小改进：（36ms -> 32ms）
1，reserve ret
效果：
Runtime: 32 ms, faster than 98.87% of C++ online submissions for Course Schedule II.
Memory Usage: 14.4 MB, less than 6.06% of C++ online submissions for Course Schedule II.
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> ret;
ret.reserve(numCourses);
vector<vector<int>> dependency(numCourses, vector<int>());
for (const auto& p : prerequisites){
int left = p[0];
int right = p[1];
dependency[left].push_back(right);
}
vector<int> searched(numCourses, 0);
for (int i=0; i<numCourses; ++i){
if (searched[i] != 2){
// cout << i << endl;
searched[i] = 1;
if (!dfs(i, dependency, ret, searched)) {
// cout << "loop" << endl;
return {};
}
}
}
return ret;
}
bool dfs(int node, vector<vector<int>>& dependency, vector<int>& ret, vector<int>& searched){
for (const auto& next : dependency[node]){
if (searched[next] == 1){
return false;
}
if (searched[next] == 0){
// cout << next << endl;
searched[next] = 1;
if (!dfs(next, dependency, ret, searched)){
return false;
}
}
}
searched[node] = 2;
ret.push_back(node);
return true;
}
};
