原文題目
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.

題目摘要

1. 你需要完成總共 numCourses 門課程，編號從 0 到 numCourses - 1。
2. 題目給予一個數組 prerequisites，其中 prerequisites[i] = [ai, bi] 表示你必須先完成課程 bi 才能修習課程 ai。
3. 題目要求：如果可以完成所有課程回傳true，否則，回傳 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.

解題思路

1. 分析問題:
   這題可以理解有向圖的循環檢測問題，先修課程的依賴關係會形成一個有向圖，如果該圖中有循環，就代表無法完成所有課程。

2. 建立鄰接表:

   • 使用鄰接表 adjList 來表示課程之間的先修依賴關係。每個課程對應一個列表，該列表包含它的後續課程。
   • 遍歷 prerequisites 將每對先修關係加入鄰接表。[ai, bi] 表示課程 bi 是課程 ai 的先修課程，表示一條從 bi 指向 ai 的邊。

3. DFS 檢查循環:

   • 定義一個 visited 數組來標記每個節點（課程）的狀態：
     • 0: 未訪問。
     • 1: 正在當前的 DFS 路徑中訪問（訪問中）。
     • 2: 訪問完成（已處理）。
   • 對每個課程執行DFS，如果在過程中某個課程的後續課程已經在訪問中，代表存在循環則回傳 false。如果沒有發現循環，則回傳 true。

4. DFS 遞迴邏輯:

   • 遍歷每個課程的後續課程，對每個後續課程再次執行 DFS，如果某個後續課程存在循環，則當前課程無法完成。
   • 若後續課程無環，則標記當前課程訪問完成，並繼續檢查其他課程。

5. 回傳結果:

   • 如果對所有課程的 DFS 都沒有發現循環，則表示可以完成所有課程，回傳true。

程式碼

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = new ArrayList<>(); //設立一個鄰接表來表示每個課程的先修關係
        
        //建立numCourses個空的課程列表
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }

        //將先修課程的依賴關係填入鄰接表：prerequisites[i] = [ai, bi]表示先修bi才能修ai
        for (int[] pair : prerequisites) {
            adjList.get(pair[1]).add(pair[0]);
        }
        
        int[] visited = new int[numCourses]; //設立一個陣列來記錄每個課程的訪問狀態：0 = 未訪問, 1 = 訪問中, 2 = 訪問完成
        
        //遍歷每個課程進行DFS檢查
        for (int i = 0; i < numCourses; i++) {
            //如果發現循環，代表無法完成所有課程，則回傳false
            if (!dfs(i, adjList, visited)) {
                return false; 
            }
        }
        
        return true; //如果所有課程無循環，則回傳true
    }
    //DFS方法檢查是否有循環
    private boolean dfs(int course, List<List<Integer>> adjList, int[] visited) {
        //如果該課程正在當前DFS路徑中訪問，代表有循環則回傳false
        if (visited[course] == 1) {
            return false;  
        }
        //如果該課程已經訪問過並且無循環直接回傳true
        if (visited[course] == 2) {
            return true; 
        }
        
        visited[course] = 1; //標記當前課程為訪問中
        
        //遍歷該課程的所有後續課程進行DFS
        for (int next : adjList.get(course)) {
            //如果某個後續課程存在循環則回傳false
            if (!dfs(next, adjList, visited)) {
                return false;
            }
        }
        
        visited[course] = 2; //標記當前課程為訪問完成，確認此課程無循環

        return true;//該課程及其後續課程無循環回傳true
    }
}

結論
這題表面上是判斷一組課程是否能夠根據先修條件全部完成，仔細思考後就能發現題目實際上就是一個有向圖檢測是否存在環的圖形問題，如果課程之間的先修關係形成了環，那就無法完成所有課程。我使用了鄰接表來構建課程的依賴關係，並用深度優先搜尋（DFS）來遍歷每門課程。為了避免重複訪問和檢測環的存在，定義了一個訪問狀態數組，將每門課程標記為未訪問、訪問中或已訪問結束。在 DFS 中，如果發現一門課程正在訪問中，則表示有環存在。透過這道題目，我學會了如何將抽象問題轉化為圖形問題，並運用 DFS 和狀態標記技術來檢測有向圖中的環，進一步加深了我對圖形應用的理解。