[LeetCode 207] Course Schedule (Medium)

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?

Example

Given n = 2, prerequisites = [[1,0]]
Return true

Given n = 2, prerequisites = [[1,0],[0,1]]
Return false

思路1 (In degree)

已知 course number, prerequisites (edge information)

1. 根据prerequisites和course number的信息创建graph

• graph: 用List[] graph = new ArrayList[courseNumbder] 的数据结构来存储
  因为course #是从0 开始，所以graph[0]:[1, 2] 表示 课程0是课程1，2的前置课。
• in-degree: 用int[] degree 的数据结构来存储

方法：
course 前置
[ 1, 0 ]
[ 2, 0]
[ 2, 1 ]
-->

graph   
[0]: [1, 2]     课程0是1，2的前置
[1]: [2]

注意：如果某些课并非任何课的前置，那么graph[x]: new ArrayList<Integer>() 为空

degree 
[0]: 0             课程0的in-degree是0
         [1]: 1
         [2]: 2

2. 用拓扑排序法遍历图，计数所有in-degree变为0的节点。当DAG为空或不存在indegree为0的节点时，停止操作。比较得到的所有in-degree == 0的节点总数，是否与总课程数相当，如果相等则表示无环。

方法：

1. 将degree为0 的课程全部加入queue中.
2. 从queue中取一个node, count++ （因为queue中都是in-degree为0的节点）
3. 在graph中找到他的后置节点，在degree中将每个后置节点in-degree – 1
4. 减一以后如果其in-degree变为0，则将其加入queue

直到queue为空

5. 判断count == numCourses，等于则表示全部上完了，为true；否则为false

public class Solution {
    /**
     * @param numCourses a total of n courses
     * @param prerequisites a list of prerequisite pairs
     * @return true if can finish all courses or false
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Write your code here
        
        if (prerequisites == null || prerequisites.length == 0) {
            return false;
        }
        
        //1. construct graph and indegree
        List[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        
        // initialize graph
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        
        for (int i = 0; i < prerequisites.length; i++) {
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
            indegree[prerequisites[i][0]]++;
        }
        
        //2. put all node with 0 indegree into a queue
        Queue<Integer> queue = new LinkedList<Integer>();
        
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.add(indegree[i]);
            }
        }
        
        //3. traverse the graph and count the course we took
        int count = 0;
        while (!queue.isEmpty()) {
            count++;
            
            int curCourse = queue.poll();
            int size = graph[curCourse].size();
            for (int i = 0; i < size; i++) {
                int nextCourse = (int)graph[curCourse].get(i);
                indegree[nextCourse]--;
                if (indegree[nextCourse] == 0) {
                    queue.add(nextCourse);
                }
            }
        }
        
        return count == numCourses;
        }
}

Solution 2 (DFS to Check if there is a cycle in the directed graph)

1. 用DFS来判断当前图中是否有环，如果有环，那么则无法找到Topological Order, 即不能完成所有课程
2. 对题目已知条件需要做预处理，需要用一个HashMap来存，preCourse vs Courses
3. 需要2个data structure来保存：
   • 整个处理过程中的 visited nodes
   • 本次dfs过程中已经加入访问路径的node recStack
4. 遍历所有课程，即 for loop through course (0 ~ N)，对每个课程都用DFS判断是否从它出发能找到环。一旦找到就说明不可能遍历完。直接返回false
5. visited nodes 是对整个所有遍历的访问节点的记录，所以不受backtracking清除标记的影响。但是 recStack是对当前路径的标记，所以需要清除。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0) {
            return true;
        }
        
        if (numCourses == 0) {
            return true;
        }
        
        //1. Generate nodeVsNeighbors map
        Map<Integer, List<Integer>> nodeVsNeighbors = new HashMap<> ();
        for (int i = 0; i < prerequisites.length; i++) {
            int course = prerequisites[i][0];
            int preCourse = prerequisites[i][1];
            
            List<Integer> courses = nodeVsNeighbors.getOrDefault (preCourse, new ArrayList<Integer> ());
            courses.add (course);
            nodeVsNeighbors.put (preCourse, courses);
        }
        
        //2. scan all course and try to find the cycle
        boolean[] visitedCourses = new boolean[numCourses];
        boolean[] recStack = new boolean[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            if (canFindCycle (nodeVsNeighbors, visitedCourses,recStack, i)) {
                return false;
            }
        }
        
        return true;
    }
    
    // if can find cycle, then there is no topological sort, then cannot finish all courses
    public boolean canFindCycle (Map<Integer, List<Integer>> nodeVsNeighbors, boolean[] visitedCourses, boolean[] recStack, int courseNum) {
        
        // order matters, if it is in recStack, no matter it is in visited or not, must return true;
        if (recStack[courseNum]) {
            //System.out.println ("2:" + courseNum);
            return true;
        }
        
        if (visitedCourses[courseNum] && !recStack[courseNum]) {
            //System.out.println ("1:" + courseNum);
            return false;
        }
        
        visitedCourses[courseNum] = true;
        recStack[courseNum] = true;
        
        for (int nextCourse : nodeVsNeighbors.getOrDefault (courseNum, new ArrayList<Integer> ())) {
            //System.out.println ("3:" + nextCourse);
            if (canFindCycle (nodeVsNeighbors, visitedCourses, recStack, nextCourse)) {
                //System.out.println ("4:" + courseNum);
                return true;
            }
        }
        
        recStack[courseNum] = false;
        //System.out.println ("5:" + courseNum);
        return false;
    }
}