給一個 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;
}
}