题目描述

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

样例1

输入: 2, [[1,0]] 
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

样例2

输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
     因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

说明

1. 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法 。
2. 你可以假定输入的先决条件中没有重复的边。

提示

1. 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
2. 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
3. 拓扑排序也可以通过 BFS  完成。

算法1

(DFS拓扑排序) $O(n + m)$

理解题意后我们发现题目就是让输出一个课程的拓扑序，这里每个课程是一个点，如果课程a依赖于课程b即b是a的先修课那么就在b到a之间连一条有向边。

拓扑序的定义是将有向图中的点进行编号，使得所有的边都由低编号指向高编号。这里有一个定理就是一个有向图存在拓扑序当且仅当它没有环。我们可以用DFS或者BFS来找到拓扑序。

而用DFS来找拓扑序的思路是这样的：

1. 因为图里没有环，所以一定存在一个点没有出边即不存在从该点指向其他点的边，这可以用反证法来证明，如果没有这样的点，那么所有的点都有出边，我们沿着出边走，因为点是有限的，我们一定会走到之前走到过的点，因而构成了环，就形成了矛盾。
2. 当我们找到这样的点后，我们将该点以及所有指向该点的边删去，并给该点赋编号n，这里n是最大的可用编号，初始时为n，然后为n - 1, n - 2,…, 1。
3. 因为图本身是没有环的，我们删去一些点和边后一定也是不存在环的，只有加边才有可能构成环。

这样找到的序列一定是该图的一个拓扑序，因为根据上述的构造过程，是不存在从高编号指向低编号的边的，因为我们是从高往低编号并且每次找到的点都是不存在出边的。

在实际实现该算法的时候我们不需要真的删去点和边，我们可以利用DFS来做到这一点，我们从一个点开始不断地进行DFS，如果遇到某个点它所有的儿子都已经被访问过了，就说明它指向的都是已被分配好的高编号的点，换句话说就是它现在可以看成没有出边了。我们就给它分配编号（加入到当前拓扑序的首部）并将它标记为已被访问过。上述的DFS过程保证了若点u和v之间存在一条由u指向v的边，那么v的DFS访问一定在u之前结束，因此保证了找到的一定是拓扑序。

上述分析的过程只适用于图中一定存在拓扑序的情况，不过若图中是包含环的，我们其实也可以在DFS的时候判断出来。具体做法是每个点不再只有 访问过 和 未被访问过 两种状态，我们再增加一个 正在访问中 的状态，即正在递归的访问它的儿子，当我们在DFS的过程中遇到了一个 正在访问中 的点，说明我们遇到了环，直接返回false。

时间复杂度

所有点和边只会被访问一次，因为有n个点，而这n个点之间在是完全图的情况下则最多可以有 $O(n^2)$ 条边，所以最坏情况下时间复杂度为 $O(n^2)$，也可以写成 $O(n + m)$，这里n是点数，m是边数。

C++ 代码

// 这里vis[i] = 0代表未被访问过，1代表已经访问完，-1代表正在访问中
class Solution {
public:
    vector<vector<int>> adjList;
    vector<int> vis;
    vector<int> res;

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        adjList = vector<vector<int>>(numCourses);
        vis = vector<int>(numCourses, 0);

        for (auto &edge : prerequisites) {
            adjList[edge[1]].push_back(edge[0]);
        }

        for (int i = 0; i < numCourses; i ++ ) {
            if (vis[i] == 0) {
                if (!dfs(i)) return vector<int>();
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }

    bool dfs(int u) {
        vis[u] = -1;
        for (auto p : adjList[u]) {
            if (vis[p] == -1) return false;
            if (vis[p] == 0) {
                if (!dfs(p)) return false;
            }
        }
        vis[u] = 1;
        res.push_back(u);
        return true;
    }
};

算法2

(BFS拓扑排序) $O(n + m)$

我们也可以利用BFS来做拓扑排序，这里我们换一种建图方式，如果课程a依赖于课程b即b是a的先修课那么就在a到b之间连一条有向边，即将算法一中的边反向。那么没有出边的点就是没有先修课或者先修课都已经修完的课，这样我们在DFS中由低往高编号就可以得到一个拓扑序。或者我们可以用BFS每次找到没有入边的点，然后删除该点和从该点出发的边，将该点加入到当前拓扑序首部，我们同样也可以得到一个拓扑序，而将该拓扑序逆序后就是答案。

因此我们可以观察到一个定理，如果对于图G有一个拓扑序P，那么我们将图G的所有边反向后，同时将P逆序得到P'，则P'也是G'的一个拓扑序。简要的证明思路如下，因为P中的边都由低编号指向高编号，那么将G中所有边反向后，所有的边都会变成由高编号指向低编号，此时我们再将P逆序，就又变成了由低编号指向高编号，因此得到了一个拓扑序。

时间复杂度

同样的，每个点和边只会被遍历一次，时间复杂度为 $O(n + m)$。

C++ 代码

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adjList(numCourses);
        vector<int> indegree(numCourses);
        for (auto &pre : prerequisites) {
            int a = pre[0], b = pre[1];
            adjList[a].push_back(b);
            indegree[b] ++ ;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i ++ ) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        vector<int> res;
        while (q.size()) {
            auto t = q.front();
            q.pop();

            for (auto course : adjList[t]) {
                if ( -- indegree[course] == 0) {
                    q.push(course);
                }
            }
            res.push_back(t);
        }
        reverse(res.begin(), res.end());
        if (res.size() < numCourses) return vector<int>();
        return res;
    }
};