207. Course Schedule - Medium

前往題目

題目心得搬運

心得

• 沒想到是用graph的形式
• 沒想到是只要看有沒有cycle就行
• 而且還能用DFS或是BFS，但因為沒想到是graph所以正常😂
• 由此可見敏銳度須繼續培養，畢竟目前才寫了50題左右
• 數組與圖之間的關係比較難想像

思路

1. 每個course都有自己的prerequisites，因此需要數組的數組以便放入各課程的prerequisite
2. 取得每個課程的prerequisites後就可以開始DFS每門課的pre是否有cycle
3. 只要有cycle代表有衝突，不可能修得了
4. 沒有的話每門課都要當成一個branch，經過的路上需要標記經過2，遇到死巷return回來的時候把每個都標記回1，這樣就知道已經路過而且沒有cycle
5. 下一門課遇到同一個pre就可以直接return true，因為已經確認過那門pre之後都沒有cycle

Code

class Solution {
    int[] visited; // Indicate if a course has visited or not
    ArrayList<Integer>[] adj; // An array to store array list of the prerequisite courses

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visited = new int[numCourses];
        adj = new ArrayList[numCourses];
        
        // Init. every course list
        for(int i = 0; i < numCourses; ++i) {
            adj[i] = new ArrayList<>();
        }
        
        // Est. prerequisites list
        for (int[] pre : prerequisites) {
            adj[pre[0]].add(pre[1]); // Add the pre to each course's pre list
        }

        // Check each course
        for (int i = 0; i < numCourses; ++i) {
            if (dfs(i) == false) return false;
        }
        return true;
    }

    public boolean dfs(int cur) {
        
        if (visited[cur] == 1) return true; // Means no cycle
        if (visited[cur] == 2) return false; // Cycle appears!

        // Passing the cur
        visited[cur] = 2;

        // Check next course
        for (int nex : adj[cur]) {
            if (dfs(nex) == false) return false;
        }

        // Going back, mark as completed
        visited[cur] = 1;
        return true;
    }
}

2024/01/17

• 有記得要看cycle
• 靠著以前的code輔助寫出來了