# 207 Course Schedule

給一正整數表示課堂總數、和二維整數矩陣表示某課需要先修另一門課，e.g. [1,2] 表示course 1 需要先修course2。

問根據提供的課堂資料，是否有可能修完所有的課呢？

2, [[1,0]  => true
2, [[1,0],[0,1]] => false

Idea 一開始想用2d boolean array表示課堂之間的關係，size為numCourses * numCourses，若(i,j)位置為true，表示課堂i需要先修課堂j。

後來又想到每個課堂可以表示為node，就可以畫成graph，上面的兩個例子分別可以畫成這樣的圖

0 -> 1

0 -> 1
  <-

此時就發現當有cycle時，就表示不可能修完所有的課。

再來就是要決定怎麼存課程之間的相依關係，最後決定用map，map裡的key為course number，value是一個List，裡面存修此門課前必修的課。

Pseudocode

visit all entries in prerequisites and create a map

visit all entries in the map
    queue of prerequesites
    while(queue is not empty)
      if prereq is in map
        if prereq's value is the same as current entry
          return false
        put prereq's value in to queue

return true

Code

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        //create map
        for(int i=0; i<prerequisites.length; i++){
            int key = prerequisites[i][0];
            if(map.get(key) != null){
                List<Integer> list = map.get(key);
                list.add(prerequisites[i][1]);
                map.put(key, list);
            }else{
                map.put(key, new ArrayList<>(Arrays.asList(prerequisites[i][1])));
            }
        }

        //visit all entries in map
        for(Map.Entry<Integer, List<Integer>> entry: map.entrySet()) {
            Queue<Integer> prereq = new LinkedList<>();
            for(int i: entry.getValue()){
                prereq.add(i);
            }
            while(!prereq.isEmpty()){
                int cur = prereq.remove(); 
                if(map.get(cur) != null){
                    List<Integer> list = map.get(cur);
                    for(int j : list){
                        if(j == entry.getKey())
                            return false;
                        else
                            prereq.add(j);
                    }
                }

            }
        }
        return true;
    }
}

這個解法可以過27/42 test cases，最後會TLE。 Time Complexity Analysis: prerequisites array can be n^2. total number of map entry should be n. each list can be as large as n-1. in the while loop, the queue can be as big as n^2. Thus, the second loop is bound by O(n^3)

Optimize 用我最一開始想的2d array紀錄，並且加上一個visited array，標記是否重複拜訪某個點，如此一來可以快速找到cycle，

class Solution {
    /*
     Pseudo Code:  {2, [0,1]}
     bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
         Construct graph
         Construct a visited array

         Go through each node
            DFS to search if there's cyle
            if there's cyle, return false

         return true
     }


     bool dfs(int courseNo, vector<int> &visitState)
     {
        if visitState is VISITING, return true; //cycle
        if visitState is VISITED, return false; //no cycle

        marked as VISITING

        for all neighbors of courseNo
            dfs(neighborNo, visitState)

        marked as VISITED

        return false;
     }

    */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[][] graph = new int[numCourses][numCourses];
        int[] visited = new int[numCourses];//0 - not visit yet, 1 - visiting, 2 - visited

        for(int i=0; i<prerequisites.length; i++){
            int courseNum = prerequisites[i][0];
            int prereq = prerequisites[i][1];
            graph[courseNum][prereq] = 1; // 1 : indicate courseNum requires prereq
        }

        for(int i=0; i<prerequisites.length; i++){
            int courseNum = prerequisites[i][0];
            if(dfs(courseNum, visited, graph))//return true if there's a cycle
                return false;
        }

        return true;
    }

    private boolean dfs(int courseNum, int[] visited, int[][] graph){
        if(visited[courseNum] == 1)//cycle
            return true;

        if(visited[courseNum] == 2)//no cycle
            return false;

        visited[courseNum] = 1;

        for(int i = 0; i<visited.length; i++){
            if(graph[courseNum][i] == 1){
                if(dfs(i, visited, graph)) return true;
            }
        }

        visited[courseNum] = 2;
        return false;
    }
}