Tag

【拓扑排序】

题目来源

210. 课程表 II

题目解读

在选修某些课程之前需要先学习某些课程，先学习的课程有数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] 表示为学习课程 ai 之前要先学习课程 bi。请你判断是否可以完成 numCourses 课程数的课程，如果可以返回任意一种课程的学习顺序，否则返回一个空数组。

解题思路

方法一：拓扑排序

本题与 207. 课程表 解法基本一致，都是考察 拓扑排序 的内容。

唯一的区别在于需要使用了一个数组 ret 来统计一种可行的课程学习顺序，我们从入度为 0 的课程编号出发，迭代的记录经过的课程编号。如果最后 ret.size() = numCourse 则表示，该数组记录的是一个可行的课程学习顺序，返回 ret，否则返回空数组。

实现代码

class Solution {
    #define maxn 2010
    vector<int> edges[maxn];
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        int i, j;
        int n = prerequisites.size();
        queue<int> q;
        int in[maxn];
        memset(in, 0, sizeof(in));
        for(i = 0; i < n; ++i){
            int u = prerequisites[i][1];
            int v = prerequisites[i][0];
            ++in[v];
            edges[u].push_back(v);
        }

        for(i = 0; i < numCourses; ++i){
            if(in[i] == 0){
                q.push(i);
            }
        }
        vector<int> ret;
        while(!q.empty()){
            int u = q.front();
            ret.push_back(u);
            q.pop();

            for(i = 0; i < edges[u].size(); ++i){
                int v = edges[u][i];
                --in[v];
                if(in[v] == 0){
                    q.push(v);
                }
            }
        }
        if(ret.size() == numCourses){
            return ret;
        }
        return {};
    }
};

复杂度分析

时间复杂度： O ( n + m ) O(n+m) O(n+m)，其中 n n n 为课程数， m m m 选修课程限制数组的长度。

空间复杂度： O ( n + m ) O(n+m) O(n+m)，课程之间建立邻接表的空间复杂度为 O ( n + m ) O(n+m) O(n+m)。广搜中使用最多 O ( n ) O(n) O(n) 的队列空间。因此总空间复杂度为 O ( n + m ) O(n+m) O(n+m)。

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出