LeetCode-210 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.

题目大意

题意同LeetCode-207 Course Schedule，但需要返回看书的顺序（如果存在多个解，则返回其中之一）。

示例

E1

Input: 2, [[1,0]] 
Output: [0,1]

E2

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

Output: [0,1,2,3] or [0,2,1,3]

解题思路

依然使用DFS来遍历所有可能性，但需要保存可能的返回结果，算法中需要使用两个数组来分别保存图节点的访问情况，其中第一个数组表示本次以K为源节点进行DFS遍历时所访问的节点，第二个数组表示在所有的访问情况中结点的访问状态。（PS:语言表达看似很复杂，实际看到代码就应该很容易理解）

复杂度分析

时间复杂度：O(|V| + |E|)

空间复杂度：O(|V| + |E|)

代码

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<unordered_set<int> > edge(numCourses);
        vector<int> res;
        //对图的边进行二维数组保存
        for(int i = 0; i < prerequisites.size(); ++i) {
            edge[prerequisites[i][0]].insert(prerequisites[i][1]);
        }
        //表示以当前访问的结点为源点进行dfs时其余结点的访问情况
        vector<bool> todo(numCourses, false);
        //表示在所有结点访问的过程中的结点被访问情况
        vector<bool> done(numCourses, false);
        for(int i = 0; i < numCourses; ++i) {
            if(!done[i] && !dfs(res, edge, todo, done, i)) {
                return {};
            }
        }
        return res;
    }
    
    bool dfs(vector<int>& res, vector<unordered_set<int> >& edge, vector<bool>& todo, vector<bool>& done, int k) {
        //若该节点在本次DFS过程中以被访问，并且本次还要访问，则代表产生环
        if(todo[k])
            return false;
        //若该结点已被完全访问，其子节点也完全被遍历过，则表示该结点为终结点
        if(done[k])
            return true;
        todo[k] = done[k] = true;
        //DFS遍历结点K的子节点
        for(unordered_set<int>::iterator iter = edge[k].begin(); iter != edge[k].end(); ++iter) {
            if(!dfs(res, edge, todo, done, *iter))
                return false;
        }
        //若满足以上条件，则代表在这个小的以K为源点的遍历过程中，无环产生
        res.push_back(k);
        //为了不影响其他DFS过程中结点的访问情况，将该位置的访问情况进行还原
        todo[k] = false;
        return true;
    }
};