Course Schedule

Q:
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
A:
就是top logical sort （CLIS上的经典代码）

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> status(numCourses, 0);// 0 as no-visited, 1 as visiting, 2 visited
        vector<vector<int>> A(numCourses, vector<int>());
        for(auto M : prerequisites)
            A[M[0]].push_back(M[1]);
        for(int i =0;i<numCourses;++i)
            if(status[i]==0 && not dfs(A, status, i))
                return false;        
        return true;
    }
private:
    bool dfs( vector<vector<int>>& A, vector<int>& S, int i)
    {
        S[i]=1;//gray out the color
        for(auto k : A[i])
        {
            if(S[k]==1)
                return false;
            if(S[k]==0 && not dfs(A,S, k))
                return false;                
        }
        S[i]=2; // mark it black
        return true;
    }
};

-------------old---------每次traversal的同时，还可以在限制条件里  删去已经满足的课程 ----------

public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
        Set<Integer> set = new HashSet();
        Map<Integer, List<Integer>>  map = new HashMap();
        for(int i =0; i<numCourses; i++)  // initialize
            map.put(i,new LinkedList<Integer>());

        for(int j =0; j<prerequisites.length;j++)  // build the set
            map.get(prerequisites[j][0]).add(prerequisites[j][1]);

        boolean foundOne = true;
        while( !map.isEmpty() && foundOne){
            foundOne = false;
            for(int key : map.keySet()){
                boolean allTaken = true;
                List constrainList = map.get(key);
                for(int k = 0;k< constrainList.size();k++) // k is the constrain class
                    if( !set.contains(constrainList.get(k))){ // get the pre-requirement for class  key
                        allTaken = false;
                        break;
                    }else{ // this constrain class (k) is already found
                        constrainList.remove(k); // delete this constrains
                        k--;
                    }
                if(allTaken){
                    foundOne = true;
                    set.add(key);
                    map.remove(key);
                    break;
                }
            }
        }
        return map.isEmpty();
    }
}
 

注意，这里，最后一个break没有加的时候，仍然会超时。


Mistakes:
 1：  当 input 为1 [] 的时候， 陷入了死循环。    原因在于忘记找到可以先上的课后，把它放到set里的同时， 还要 map.remove()了

2：   第一遍解法的时候，如果 最后一个break没有加的时候，仍然会超时。   按理说不应该呀？？？