207. Course Schedule ----M !!!

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

 

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 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.

 

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

A:
就是topological sort （CLIS上的经典代码）

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> Color(numCourses, 0); //0 for white, 1 for gray, and 2 for black
        unordered_map<int, vector<int>> M;
        for (auto pre : prerequisites) {
            M[pre[0]].push_back(pre[1]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (not dfs(M, Color, i))
                return false;
        }
        return true;
    }
private:
    bool dfs(unordered_map<int, vector<int>>& M, vector<int>& Color, int i) {
        if (Color[i] == 2) {
            return true;
        }
        if (Color[i] == 1) {
            return false;
        }
        Color[i] = 1; // mark gray now,
        for (int val : M[i]) {
            auto res = dfs(M, Color, val);
            if (not res)
                return false;
        }
        Color[i] = 2;
        return true;
    }
};

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

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没有加的时候，仍然会超时。   按理说不应该呀？？？