207. Course Schedule

Link

Solution

這題的作法有BFS跟DFS兩種。

DFS的作法: 根據每堂課，往上去尋找它的course path，看看有沒有形成loop。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, Boolean> canFinish = new HashMap<>();
        for(int i = 0; i < numCourses; i++){
            if(!dfs(canFinish, i, prerequisites)) return false;
        }
        return true;
    }
    
    public boolean dfs(HashMap<Integer, Boolean> canFinish, int course, int[][] prerequisites){
        if(canFinish.containsKey(course)) return canFinish.get(course);
        
        canFinish.put(course, false);
        
        for(int[] pair : prerequisites){
            if(pair[0] == course){
                dfs(canFinish, pair[1], prerequisites);
                if(!canFinish.get(pair[1])){
                    return false;
                }
                
            }
        }
        canFinish.put(course, true);
        return true;
    }
}

BFS的作法:

先找出不用其他課就能上的課。(degree == 0)

再透過BFS尋找所有找出能夠上的課，然後標記為上過了。 (放到queue中)

再看看這些上過的課是否能讓其他課也上過了。 (將相對應的degree -1)

依此類推看看能不能把所有的課上完。

因為BFS的做法比較快。(節省了不必要的分支計算)

    public boolean canFinish(int numCourses, int[][] prerequisites) {
            int[] degrees = new int[numCourses]; //degree[i] : for courses i, how many prerequistie classes?
            ArrayList<Integer>[] dependence = new ArrayList[numCourses]; //dependence[i] : classes depend on i
            
            int count = 0;
            Queue<Integer> takenClasses = new LinkedList<Integer>();
            
            for(int i=0; i < numCourses; i++){
                dependence[i] = new ArrayList();
            }
            
            for(int[] pre : prerequisites){
                degrees[pre[0]]++;
                dependence[pre[1]].add(pre[0]);
            }
            
            
            for(int i = 0; i < numCourses; i++){
                if(degrees[i] == 0){
                    takenClasses.add(i);
                    count++;
                }
            }
            while(!takenClasses.isEmpty()){
                int takenClass = takenClasses.poll();
                for(Integer i : dependence[takenClass]){
                    degrees[i]--;
                    if(degrees[i] == 0){
                        takenClasses.add(i);
                        count++;
                    }
                }
            }
            if(count == numCourses) return true;
            return false;
            
        }