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

:::info
:information_source: 題目 : Course Schedule, 類型 : graph , 等級 : medium
日期 : 2023/04/09，2023/05/16，2023/07/14，2023/10/27，2023/12/08，2024/02/14，2024/09/20，2024/10/11
:::

### 嘗試
2023/05/16

再visit兩次 = 形成迴圈
只要一旦不符合dfs 就回傳錯誤


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        record = collections.defaultdict(list)
        visited = set()
        for cor, pre in prerequisites:
            record[cor].append(pre)
        
        def dfs(c):
            if record[c] == []:
                return True
            if c in visited:
                return False
            
            visited.add(c)
            for p in record[c]:
                if not dfs(p):
                    return False
    
            # 通過
            record[c] = []        
            return True
        
        for c in range(numCourses):
            if not dfs(c):
                return False
        return True

2023/07/14
只會有一個錯誤的條件，(以dfs為例)如果在dfs過程中，**碰到正在visited中的課程**(也就是在dfs這條路上的課程)，必定錯誤，因為代表這條路有互相引用的情況
就是要遍歷每一個課程，然後**不斷檢查這門課程前面所有的pre課程**，任何衝突都沒有發生就可以回傳True
這類**if not dfs()就回傳False，代表是"嚴格dfs"**，如果有任何一階回傳False，所有都會變False

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = defaultdict(list)
        for cour, pre in prerequisites:
            graph[cour].append(pre)
        
        visited = set()
        def dfs(cour):
            if cour in visited:
                return False
            if not graph[cour]: # 沒有先修課程
                return True

            visited.add(cour)

            for pre in graph[cour]:
                if not dfs(pre):
                    return False
            
            # 走到這裡 代表這個課程前面的路(pre)沒有問題
            # 為了加快速度
            graph[cour] = []
            visited.remove(cour)
            return True

        for cour in range(numCourses):
            if not dfs(cour):
                return False
        return True

2023/10/27

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        record = defaultdict(list)
        for cour, pre in prerequisites:
            record[cour].append(pre)
    
        
        def dfs(cour, visited):
            if not record[cour]:
                return True
            
            if cour in visited:
                return False
            
            visited.add(cour)
            for pre in record[cour]:
                if not dfs(pre, visited):
                    return False
            
            record[cour] = []
            return True
        
        for i in range(numCourses):
            if not dfs(i, set()):
                return False
        return True

2023/12/08

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        for c, p in prerequisites:
            graph[c].append(p)

        visited = set()

        def dfs(cour):
            visited.add(cour)
            for pre in graph[cour]:
                if pre in visited:
                    return False
                if not dfs(pre):
                    return False
            visited.remove(cour)
            graph[cour] = []
            return True
        
        for n in range(numCourses):
            if not dfs(n):
                return False
        return True

2024/02/14

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = collections.defaultdict(list)
        for cou, pre in prerequisites:
            graph[cou].append(pre)
        
        visited = set()
        def dfs(c):
            if not graph[c]:
                return True 
            if c in visited:
                return False
            
            visited.add(c)
            for pre in graph[c]:
                if not dfs(pre):
                    return False

            visited.remove(c)
            graph[c] = [] # optimization
            return True
        
        for c in range(numCourses):
            if not dfs(c):
                return False
        
        return True

2024/09/20
會需要remove，是因為可能會有

         1
0   -          -   3
         2
我們是從3走回去，用dfs會先走3-1-0，再來走3-2-0，
如果沒有remove的話，0會被標記為已經走過，會錯誤

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        record = defaultdict(list)
        for cor, pre in prerequisites:
            record[cor].append(pre)
        
        def dfs(n, visited):
            if n in visited: # circle
                return False
            if not record[n]: # None
                return True

            visited.add(n)
            for pre in record[n]:
                if not dfs(pre, visited):
                    return False

            visited.remove(n)
            record[n] = []

            return True
        
        for n in range(numCourses):
            if not dfs(n, set()):
                return False
        return True

2024/10/11
拜託記得remove，同一個course的dfs也會有相同的pre

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        record = defaultdict(list)
        for cour, pre in prerequisites:
            record[cour].append(pre)
        
        for c in range(numCourses):
            visited = set()
            if not self.dfs(c, visited, record):
                return False
        return True

    def dfs(self, c, visited, record):
        if c in visited:
            return False
        if not record[c]:
            return True
        
        visited.add(c)
        for pre in record[c]:
            if not self.dfs(pre, visited, record):
                return False
        
        visited.remove(c)
        record[c] = []
        return True

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

如果圖形如下面那張圖所示，主函數的for迴圈從4開始思考，會直接通過，再來從3開始思考，會先visit.add(3)，考慮4，再visit.remove(3)，最後回傳true給主函數，讓他可以繼續往1去思考

時間複雜度O(n)
創建 preMap 字典的時間複雜度為 O(n)，其中 n 是課程數量。
DFS 遍歷所有的課程節點，時間複雜度為 O(n)。
在 DFS 遍歷過程中，每個課程節點最多只會被訪問一次，因此整個算法的時間複雜度為 O(n)。

空間複雜度O(n)
preMap 字典的空間複雜度為 O(n)。
visit 集合的空間複雜度為 O(n)。
DFS 遞迴深度最多為 n，因此整個算法的空間複雜度為 O(n)。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        preMap = { i : [] for i in range(numCourses) } # 創建空dict
        for course, prere in prerequisites: # 創建course -> prere
            preMap[course].append(prere)

        visit = set()
        def dfs(course):
            if course in visit:
                return False
            if preMap[course] == []:
                return True

            visit.add(course)
            for pre in preMap[course]:
                if not dfs(pre): 
                    return False
            visit.remove(course)
            preMap[course] = []
            return True

        for course in range(numCourses):
            if not dfs(course):
                return False
            else:
                return True

---

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

:::

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

:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=EgI5nU9etnU
https://blog.csdn.net/fuxuemingzhu/article/details/82951771
Provided by. NeetCode & 负雪明烛

###### tags: `graph` `medium` `leetcode` `值得再想`