[LeetCode] Course Schedule II

Course Schedule II

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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

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 the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

解題思路：

1、首先將邊轉化成鄰接表的形式，然後逐步找那些沒有前驅課程的課，若找到一門課沒有前驅課，加入結果中，然後在圖中刪除這條邊。

class Solution {
public:
    vector findOrder(int numCourses, vector>& prerequisites) {
        vector result;
        if(numCourses<=0){
            return result;
        }
        //將圖轉化成鄰接表的形式。
        vector> graph(numCourses, set());
        for(int i=prerequisites.size() - 1; i>=0; i--){
            graph[prerequisites[i].first].insert(prerequisites[i].second);
        }
        bool flag[numCourses];  //標記是否已經加到了result裡面了
        memset(flag, 0, sizeof(bool) * numCourses);
        while(result.size()時間復雜度為O(n^2)，比較慢，雖然AC了，但是花了1492ms。
 
2、可以采用空間換時間的辦法，記錄一個反向圖，若找到一門課程後，直接刪除對應的邊，而無需遍歷整張圖。另外，記錄當前還剩下的那些節點。空間加倍，時間為591ms。
 
class Solution {
public:
    vector findOrder(int numCourses, vector>& prerequisites) {
        vector result;
        if(numCourses<=0){
            return result;
        }
        //將圖轉化成鄰接表的形式。
        vector> graph(numCourses, set());
        vector> reverseGraph(numCourses, vector());    //反向圖
        for(int i=prerequisites.size() - 1; i>=0; i--){
            graph[prerequisites[i].first].insert(prerequisites[i].second);
            reverseGraph[prerequisites[i].second].push_back(prerequisites[i].first);
        }
        set leftNode;  //還剩下哪些節點
        for(int i=0; i::iterator it=leftNode.begin(); it!=leftNode.end(); it++){
                if(graph[*it].empty()){
                    index = *it;
                    break;
                }
            }
            if(index<0){
                break;
            }
            result.push_back(index);
            leftNode.erase(index);
            //清除所有以該課程為前驅的邊
            for(int i=0; i