210. Course Schedule II

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;
    }
};