Leetcode題解 Python & C#：五月挑戰DAY29 Course Schedule

給一個 numCourses 代表從編號 0 到 numCourses 的課程。有先修要求 prerequisites，其中元素為[a, b]代表要先修完 b 才能修 a 課程。

回傳 true 如果可以修完所有課程，否則 false。

一旦先修課程形成了迴圈，如：[a, b][b, a]，那就無法完成所有課程。

這裡的課程數最多有 100000 個，數目很大，要是使用暴力破解會有超時的可能。

如果使用先修數作排列，少的先修，多的後修，但這樣可能用上 O(N^2) 的時間，直接放棄。

先串起 N 個課程，像是N-ary Tree或是Linked List等，再檢查有無迴圈產生，會用 O(N) 時 O(N) 空。

用 memo 紀錄到過的 node，如果往下的過程碰到的 node 出現在 memo 裡面，則代表有接回頭，頭尾相接就回傳 false。

用 DFS 去搜尋，如果到底，也就是沒有後續課程，那代表該條搜尋路線是沒有迴圈產生，是安全路線，之後若 DFS 來到安全路線，也不必再往下尋找。

我在想那個題目所講的方式到底是什麼？後來看懂了，大部分的解答都是用提示的想法出發。

那就是做拓樸排序，也就是把有向圖(有方向關係，如先修)，轉換成排序。如果有環出現，就無法轉換。(參考)

找第一點開始，也就是沒有先修課程的課程。往下尋找，每個點到訪次數不能超過 numCourses。這樣算暴力破解法嗎？

Python

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

        def dfs(node):
            if node in this_memo: return False
            this_memo.add(node)              
            if not all([dfs(each) for each in nodeMap[node] if each not in memo]):
                return False
            memo.add(node)    
            return True
        
        for root in range(numCourses):
            if root not in memo and not dfs(root): return False
            
        return True

C#

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        var safe_nodes = new HashSet();
        var path = new HashSet();
        var nodeMap = new Dictionary>();
        
        for(int i = 0; i < numCourses; i++)
            nodeMap[i] = new List();        
        foreach(var pair in prerequisites)
            nodeMap[pair[1]].Add(pair[0]);
               
        bool DFS(int node)
        {
            if(path.Contains(node)){return false;}
            path.Add(node);
            for(int i = 0; i < nodeMap[node].Count; i++)
                if(!(safe_nodes.Contains(nodeMap[node][i])))
                {
                    if(!(DFS(nodeMap[node][i]))){return false;}
                }
            safe_nodes.Add(node);
            return true;            
        }
        
        for(int i = 0; i < numCourses; i++)
        {
            if(!(safe_nodes.Contains(i)))
            {
                if (!DFS(i))
                {
                    return false;
                }
            }
        }
        
        return true;
    }
}