描述

为了毕业你需要选择 n 门课程，这 n 门课程中存在一定的依赖关系，例如想要完成 B 课程，必须先完成 A 课程，请你找出一个可以完成全部课程的顺序，如果无论如何选择都无法完成全部课程则返回空数组。

依赖关系以如下方式输入：
[[2,1],[3,2]]
即要完成课程 2 ，必须先完成 1 ， 要完成课程 3 ，必须先完成课程 2，答案 [1,2,3] 即可。
但也可能出现类似
[[2,1],[1,2]]
要完成课程 2 ，必须先完成 1 ，要完成课程 1 ，必须先完成课程 1 ，则无解，返回一个空数组即可。

数据范围： 1 \le n \le 2000 \1≤n≤2000  ，依赖关系的数量满足 0 \le m \le n*(n-1) \0≤m≤n∗(n−1)  ，保证不会有一组一模一样的依赖关系。

示例1

输入： 
[[1,0],[2,1]],3
复制
返回值： 
[0,1,2]
复制

示例2

输入： 
[[1,0],[2,1]],4
复制
返回值： 
[0,1,2,3]
复制
说明： 
返回 [3,0,1,2] ，[0,3,1,2] , [0,1,3,2]  也都合法

示例3

输入： 
[[1,0],[0,1]],2
复制
返回值： 
[]
复制
说明： 
  存在环

解题思路：
本题是典型的拓扑排序问题。
什么是拓扑排序呢？直观地说就是，把有向无环图「拉平」，且这个「拉平」的图所有箭头方向都是一致的。

本题中课程的依赖关系，正好可以构建有向无环图。具体实现步骤如下：
1、使用邻接表建图。索引为from，即前置课程，邻接数组为依赖这个前置课程的课程列表
2、图的遍历。一次遍历所有课程的邻接数组；
3、判断是否有环。遍历的过程中记录每条遍历路径，如果单条遍历路径上有重复的点即存在环；
4、将有向无环图的后序遍历结果反转就是拓扑排序结果。
后序遍历本身是左右根，但我们需要输出的是课程顺序，根节点实际为前置课程，需要最早输出，所以需要将后序遍历结果反转。
当然，直接在前序遍历位置记录结果也是可以的。
class Solution {
public:
    // 1、使用邻接表建图
    // 2、图的遍历
    // 3、判断是否有环
    // 4、将有向无环图的后序遍历结果反转就是拓扑排序结果
    vector<vector<int>>graph; //邻接表
    vector<bool>visit; // 记录访问标志，防止重复访问
    vector<int>path; // 记录访问路径，以此判断是否有环
    vector<int>res; // 记录最后的输出结果
    bool bad = false; // 记录是否有环
    void makeGraph(vector<vector<int> >& prerequisites)
    {
        int len = prerequisites.size();
        for (int i = 0; i < len; i++) {
            int from = prerequisites[i][1];
            int to = prerequisites[i][0];
            graph[from].push_back(to);
        }
    }
    //遍历节点t的邻接表
    void bfs(vector<vector<int> >& graph, int t)
    {
        if (find(path.begin(), path.end(), t) != path.end()) {
            bad = true;
            return;
        }
        if (visit[t]) {
            return;
        }
        visit[t] = true;
        path.push_back(t);
        int len = graph[t].size();
        for (int i = 0; i < len; i++) {
            bfs(graph, graph[t][i]);
        }
        path.pop_back();
        res.push_back(t);

    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prerequisites int整型vector<vector<>> 
     * @param n int整型 
     * @return int整型vector
     */
    vector<int> findOrder(vector<vector<int> >& prerequisites, int n) {
        // write code here
        graph.resize(n);
        visit.resize(n, false);
        makeGraph(prerequisites);
        for (int i = 0; i < n; i++) {
            bfs(graph, i);
        }
        if (bad) {
            return {};
        }
        reverse(res.begin(), res.end());
        return res;
    }
};