LeetCode -- Course Schedule

LeetCode -- Course Schedule

題目描述：


There are a total of n courses you have to take, labeled from 0 to n - 1.


Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]


Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?


For example:


2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.


2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.


選課問題，需要選n門課，已知依賴關系為二維數組[{1,0},{0,2},{x,y}..]，表示課程0依賴課程1（要選0必須先選1），課程0依賴課程2，課程x依賴課程y。課程id的取值范圍是[0,n)。


思路：
每個課程看作一個節點，依賴關系數組其實是一個圖結構。對於[{0,1},{2,3}]這個依賴數組來說，其實相當於圖中的0->1 , 2->3，只要不存在環，選課操作就是可以繼續的。
1. 使用referencing[0...n-1]來存當前課程所依賴其他課程的數量
2. 使用標記數組selections[0...n-1]來標記課程selections[i]是否已被選
3. 每次遍歷referencing數組，找出依賴數為0並且還沒有被選的課，這些課程id將被選擇並放入集合S；然後遍歷S，在依賴關系圖中找到誰依賴了S[i]，拿到這個課程id: course，然後用於更新引用數組：referencing[course]--，重復步驟1。
4. 直到referencing中沒有元素0或選夠了n門課為止。




實現代碼：

public class Solution {
    public bool CanFinish(int numCourses, int[,] prerequisites) 
    {
        var row = prerequisites.GetLength(0);
    	if(row < 2){
    		return true;
    	}
    	
    	var referencing = new int[numCourses];
    	var selections = new bool[numCourses];
    	for(var i = 0;i < row; i++)
    	{
    		referencing[prerequisites[i,0]] ++;
    	}
    	
    	var c = 0;
    	while(c < numCourses){
    		
    		// find out which courses not referencing others
    		var selected = new List();
    		for(var i = 0;i < referencing.Length; i++){
    			if(referencing[i] == 0 && !selections[i])
    			{
    				// select this course
    				c++;
    				selections[i] = true;
    				selected.Add(i);
    			}
    		}
    		
    		if(selected.Count == 0)
    		{
    			break;
    		}
    		
    		// find out which ones referencing this course then update referencing counter
    		foreach(var s in selected){
    			for(var j = 0; j < row; j++){
    				if(prerequisites[j,1] == s){
    					referencing[prerequisites[j,0]] --;
    				}
    			}
    		}
    	}
    	
    	return c >= numCourses;    
    }
}