LeetCode #210: Course Schedule I

Problem

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.
You may assume that there are no duplicate edges in the input prerequisites.

题意

题目释义参见LeetCode#207: Course Schedule。而这道题不同的地方在于要输出学习课程的序列。

分析

有了上一题的基础，事情就变得非常简单了：我们只需要在上一题的代码中做一点微小的改动，即可满足本题的要求。
下面给出两个算法各自的代码。

Code

拓扑排序

//Runtime: 19ms
//改动的地方已经标记出来了
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        _iniInDegree(numCourses, prerequisites);
        _iniOutTable(numCourses, prerequisites);
        for (int i = 0; i < numCourses; i++){
            int j = 0;
            for (; j < numCourses; j++){
                if (inDegree[j] == 0)   break;
            }
            if (j == numCourses){
                //Here
                result.clear();
                return result;
            }
            inDegree[j] = -1;
            result.push_back(j);
            for (int k = 0; k < outTable[j].size(); k++)
                inDegree[outTable[j][k]]--;
        }
        //Here
        return result;
    }
private:
    vector<int> inDegree;
    vector<vector<int>> outTable;
    vector<int> result;  //Here
    void _iniInDegree(int numCourses, vector<pair<int, int>>& prerequisites){
        inDegree.resize(numCourses);
        for (int i = 0; i < numCourses; i++)
            inDegree[i] = 0;
        for (int i = 0; i < prerequisites.size(); i++)
            inDegree[prerequisites[i].first]++;
    } 
    void _iniOutTable(int numCourses, vector<pair<int, int>>& prerequisites){
        outTable.resize(numCourses);
        for (int i = 0; i < prerequisites.size(); i++)
            outTable[prerequisites[i].second].push_back(prerequisites[i].first);
    }
};

DFS

//Runtime: 16ms
//Here
bool _cmp(const pair<int, int>& a, const pair<int, int>& b){
        return a.second > b.second;
}
class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        curPost = 0;  //Here
        _iniOutTable(numCourses, prerequisites);
        visited.resize(numCourses);
        onpath.resize(numCourses);
        for (int i = 0; i < numCourses; i++)
            visited[i] = onpath[i] = false;
        
        for (int i = 0; i < numCourses; i++){
            /* 在C++中，进行与运算时，如果第一个表达式的值是false，则后面的表达式都不用判断；否则，继续判断下一个表达式 */
            if (!visited[i] && _dfs(i)){
                //Here
                result.clear();
                return result;
            }
        }
        //Here
        _getResult();
        return result;
    }
private:
    vector<vector<int>> outTable;
    vector<bool> visited;
    vector<bool> onpath;
    //Here，记录每个点最后一次访问的时间，在有向无环图中，A->B，则A的post值要比B大（因为DFS先离开B再离开A）
    vector<pair<int, int>> post; //first = v, second = curPost
    vector<int> result;
    int curPost;
    void _iniOutTable(int numCourses, vector<pair<int, int>>& prerequisites){
        outTable.resize(numCourses);
        for (int i = 0; i < prerequisites.size(); i++)
            outTable[prerequisites[i].second].push_back(prerequisites[i].first);
    }
    bool _dfs(int v){
        if (visited[v]) return false;
        visited[v] = onpath[v] = true;
        for (int i = 0; i < outTable[v].size(); i++){
            /* 在C++中，进行或运算时，如果第一个表达式的值是true，则后面的表达式都不用判断；否则，继续判断下一个表达式 */
            if (onpath[outTable[v][i]] || _dfs(outTable[v][i]))
                return true;
        }
        /* return false */
        _postVisit(v);
        return onpath[v] = false;
    }
    //Here
    void _postVisit(int v){
        post.push_back(pair<int, int>(v, curPost));
        curPost++;
    }
    void _getResult(){
        //注意，要对post值进行降序排列
        sort(post.begin(), post.end(), _cmp);
        for (int i = 0; i < post.size(); i++)
            result.push_back(post[i].first);
    }
};