#207. Course Schedule

題目描述

給你一份課程列表，列表上的課程數量為numCourses，課程編號為0到numCourses-1，你必須將所有課程學習完畢。另外給你一份前置課程的陣列prerequisites，prerequisites[i] = [a_i, b_i]表示如果要學習a_i課程就必須先學習b_i。

舉例來說，[0, 1]表示你必須先學習課程1才能學習課程0。

如果可以完成所有課程，回傳true，反之則回傳false。

限制條件

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
每個課程前置需求組合都是唯一的。

解題思路

首先先來了解完成所有課程的意思，假設有10個課程，彼此之間沒有前置關係的話，那麼就可以一個一個完成，反之如果出現了前置課程矛盾的情況下就沒辦法完成所有課程。

舉例來說，如果前置課程的條件是[0, 1]、[1, 0]，要完成課程0必須先完成課程1，但是要完成課程1則必須先完成課程0，這種彼此矛盾的前置條件就會讓課程無法完成。或者是說這樣的情況[0, 1]、[1, 2]、[2, 0]，同樣也無法完成所有的課程。

所以這一題的重點在於如何判斷課程之間是否存在矛盾的前置條件關係。

發生前置課程矛盾時，矛盾的課程之間會形成一個環，所以從圖論的角度來看就是所謂的有向有環圖，反之能夠順利完成的課程表則是有向無環圖。因此可以使用拓樸排序來解決這個問題。

DFS

直覺的方式是利用DFS來檢查是否存在閉環。

public class Solution {
    public class TreeNode{
        public int Val;        
        public List<TreeNode> Children;
        public TreeNode(int val){
            Val = val;            
            Children = new List<TreeNode>();
        }
    }
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        if(prerequisites.Length<2) return true;
		// 為課程建立TreeNode
        var nodes = new Hashtable();
        for(int i=0;i<numCourses;i++) nodes.Add(i,new TreeNode(i));
		// 連接課程
        foreach(var i in prerequisites){
            var n0 = (TreeNode) nodes[i[0]];
            var n1 = (TreeNode) nodes[i[1]];
            n0.Children.Add(n1);
        }
		//檢查是否存在閉環
        var clear = new HashSet<int>();
        for(int i=0;i<numCourses;i++){
            if(clear.Contains(i)) continue;
            var visited = new HashSet<int>();
            var n = (TreeNode) nodes[i];            
            if(HasCycle(n,visited,clear))return false;                       
        }
        return true;
    }
    public bool HasCycle(TreeNode node,HashSet<int> visited,HashSet<int> clear){
		//如果節點已經標示為通過，則不用繼續往下撿查
        if(clear.Contains(node.Val)) return false;
		//如果節點尚未標示通過，但是重複訪問，則存在閉環。
        if(visited.Contains(node.Val)) return true;
		//將節點標示為已訪問
        visited.Add(node.Val);
		//繼續檢查子節點
        foreach(var i in node.Children){
            if(HasCycle(i,visited,clear)) return true;
        }
		//如果子節點沒有問題，表示可以將其標示為通過。
        clear.Add(node.Val);
        return false;
    }
}

複雜度分析：

時間複雜度：建立節點花掉n的時間，連接節點花掉m的時間，DFS花掉n的時間，總時間為2n+m，因此時間複雜度為O(n)。
空間複雜度：建立節點並儲存花掉n的空間，將節點標示為通過最差會花掉n的空間，總占用空間為2n，因此空間複雜度為O(n)。

Kahn’s Algorithm (BFS)

Kahn’s演算法是一種拓樸排序的演算法，它的核心概念是排除法，透過不斷的排除進入點為0的節點來進行圖的排序。進入點為0的節點在圖中就是最高級的父節點，擁有1個父節點的子節點它的進入點就為1，以此類推。 Kahn’s演算法的步驟如下：

先將進入點為0的節點存入Queue中。
取出Queue中的節點放入排序結果中，並且減去節點的子節點的進入點。
如果子節點在減去進入點後，進入點數量為0，則將子節點放入Queue中。
重複2、3步驟，直到Queue清空。
如果所有節點都處理完畢，則為有向無環圖，反之有節點無法處哩，則閉環存在。

所以，Kahn’s演算法可以幫助我們去判斷課程表中是否存在閉環，如果閉環存在則代表前置課程有矛盾，課程表無法完成。

public class Solution {
	// TreeNode Structure
    public class TreeNode{
        public int Val;
        public int Indegree;
        public List<TreeNode> Children;
        public TreeNode(int val){
            Val = val;
            Indegree = 0;
            Children = new List<TreeNode>();
        }
    }
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        if(prerequisites.Length<2) return true;
		// 建立節點
        var nodes = new Hashtable();
        for(int i=0;i<numCourses;i++) nodes.Add(i,new TreeNode(i));
		// 連接節點，並且統計進入點的數量
        foreach(var i in prerequisites){
            var n0 = (TreeNode) nodes[i[0]];
            var n1 = (TreeNode) nodes[i[1]];
            n0.Children.Add(n1);
            n1.Indegree++;
        }
		// Kahn’s Algorithm
		// 將進入點為0的節點放入Queue中
        var q = new Queue<TreeNode>();
        for(int i=0;i<numCourses;i++){
            var n = (TreeNode) nodes[i];            
            if(n.Indegree==0){
                 q.Enqueue(n);
                 nodes.Remove(n.Val);
            }
        }
		// 排除進入點為0的節點。
        while(q.Count!=0){
            var n = q.Dequeue();
			//減去子節點的進入點數量。
            foreach(var i in n.Children){
                i.Indegree--;
				//子節點的進入點為0，則放入Queue中。
                if(i.Indegree==0){
                    q.Enqueue(i);
                    nodes.Remove(i.Val);
                }
            }
        }
		// 判斷是否能夠完成課程表
        if(nodes.Count!=0) return false;
        return true;
    }
}

複雜度分析：

時間複雜度：建立節點花掉n的時間，連接節點花掉m的時間，將節點放如Queue中花掉n的時間，排除節點花掉n的時間，總時間為3n+m，因此時間複雜度為O(n)。
空間複雜度：建立節點並儲存花掉n的空間，將節點放入Queue中最差會花掉n的空間，總占用空間為2n，因此空間複雜度為O(n)。

Follow-up

學習重點

Topological Sort
DFS
BFS (Kahn’s Algorithm)