康瑞部落

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<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> result;
        if(numCourses<=0){
            return result;
        }
        //将图转化成邻接表的形式。
        vector<set<int>> graph(numCourses, set<int>());
        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()<numCourses){
            int index = -1;//表示要加入result的graph下标
            for(int i=0; i<numCourses; i++){
                if(!flag[i] && graph[i].empty()){   //表示没有前驱的课程
                    index = i;
                    break;
                }
            }
            if(index<0){
                break;
            }
            result.push_back(index);
            flag[index]=true;
            //清除所有以该课程为前驱的边
            for(int i=0; i<numCourses; i++){
                graph[i].erase(index);
            }
        }
        if(result.size() < numCourses){
            result.clear();
        }
        return result;
    }
};

时间复杂度为O(n^2)，比较慢，虽然AC了，但是花了1492ms。

2、可以采用空间换时间的办法，记录一个反向图，若找到一门课程后，直接删除对应的边，而无需遍历整张图。另外，记录当前还剩下的那些节点。空间加倍，时间为591ms。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> result;
        if(numCourses<=0){
            return result;
        }
        //将图转化成邻接表的形式。
        vector<set<int>> graph(numCourses, set<int>());
        vector<vector<int>> reverseGraph(numCourses, vector<int>());    //反向图
        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<int> leftNode;  //还剩下哪些节点
        for(int i=0; i<numCourses; i++){
            leftNode.insert(i);
        }
        while(!leftNode.empty()){
            int index = -1;
            for(set<int>::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<reverseGraph[index].size(); i++){
                graph[reverseGraph[index][i]].erase(index);
            }
        }
        if(!leftNode.empty()){
            result.clear();
        }
        return result;
    }
};