# **Leetcode筆記(Course Schedule II)**

:::info
:information_source: 題目 : Course Schedule II, 類型 : graph , 等級 : medium
日期 : 2023/05/18，2023/07/14，2023/09/04，2023/11/26，2023/12/04，2024/04/04
:::

### 嘗試
2023/07/14
不太確定為什麼錯誤
2023/09/04
主要是需要同時檢查有無重複(visited)，也要排出路徑(重點是有多種可能)，所以也需要另外一個set(done)來記錄，如果已經被放到路徑裡的node，就不用再去查找

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        for cour, pre in prerequisites:
            graph[cour].append(pre)
        
        visited, done = set(), set()
        def dfs(cour):
            if cour in visited:
                return False
            # 需要檢查這個cour有沒有已經在路徑裡了
            if not graph[cour] and not cour in done:
                path.append(cour)
                done.add(cour)
                return True
            
            visited.add(cour)

            for pre in graph[cour]:
                if not dfs(pre):
                    return False
            
            # 需要檢查這個cour有沒有已經在路徑裡了
            if not cour in done:
                path.append(cour)
                done.add(cour)
            visited.remove(cour)
            graph[cour] = [] # 加快 已經檢查過了就不用再檢查

            return True


        path = []
        for cour in range(numCourses):
            if not dfs(cour):
                return None
        return path

2023/11/26

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = collections.defaultdict(list)
        for c, p in prerequisites:
            graph[c].append(p)
        
        visited = set() 
        path = list()
        done = set() 

        def dfs(c):
            if c in done:
                return True
            if c in visited:
                return False
            
            visited.add(c)

            for pre in graph[c]:
                if not dfs(pre):
                    return False
            
            path.append(c)
            done.add(c)

            return True

        for c in range(numCourses):
            if not dfs(c):
                return []
        return path

2023/12/04

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = collections.defaultdict(list)
        for c, p in prerequisites:
            graph[c].append(p)
        
        visited, done, res = set(), set(), list()

        def dfs(c):
            if c in done:
                return True
            if c in visited:
                return False
            
            visited.add(c)
            for p in graph[c]:
                if not dfs(p):
                    return False
            
            if c not in done:
                res.append(c)
                done.add(c)
            visited.remove(c)

            return True

        for c in range(numCourses):
            if not dfs(c):
                return None
        return res

2024/04/04

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        record = collections.defaultdict(list)
        for cour, pre in prerequisites:
            record[cour].append(pre)
        
        done = set() # no violation but already added
        res = []
        visited = set()

        def dfs(c):
            if c in done:
                return True
            if c in visited:
                return False

            visited.add(c)
            for pre in record[c]:
                if not dfs(pre):
                    return False
            
            if c not in done:
                res.append(c)
                done.add(c)
            visited.remove(c)

            return True


        for c in range(numCourses):
            if not dfs(c):
                return []
        return res

---
### **優化**

時間複雜度：
該算法使用DFS遍歷圖，其中每個節點和邊都只訪問一次。在最壞的情況下，需要遍歷所有的課程節點和它們的先修課程，因此時間複雜度為O(V + E)，其中V是課程節點的數量，E是先修課程的數量。

空間複雜度：
該算法使用了一個記錄先修課程的字典（record），以及一個長度為numCourses的列表（visited）來記錄每個課程的狀態。在最壞的情況下，需要存儲所有的課程和它們的先修課程，因此空間複雜度為O(V + E)，其中V是課程節點的數量，E是先修課程的數量。

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        record = collections.defaultdict(list)
        for cor, pre in prerequisites:
            record[cor].append(pre)
        
        # -1 : 未上課 / 0 : 上課中 / 1 : 上完課(這條路可行)
        visited = [-1] * numCourses        


        def dfs(c, visited, res):
            # 代表這條路上有一個cor的pre已經被找過了(形成loop)
            if visited[c] == 0:
                return False
            if visited[c] == 1:
                return True

            visited[c] = 0
            for pre in record[c]:
                if not dfs(pre, visited, res):
                    return False
            
            # 代表這個c的pre都可以完成
            visited[c] = 1
            # 最先append的會是最pre的課程
            res.append(c)

            return True


        res = []
        for c in range(numCourses):
            # False : 代表有任一個course的pre無法完成
            if not dfs(c, visited, res):
                return []
        return res

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=ox6L7Cg0Log&ab_channel=Michelle%E5%B0%8F%E6%A2%A6%E6%83%B3%E5%AE%B6
Provided by. Michelle小梦想家

###### tags: `graph` `medium` `leetcode` `待解`