题意

给点之间的依赖关系，求拓扑排序

限制：

点的个数不大于2000

方法

循环遍历(TLE)

每次枚举点，找入度为零的，找到则标记。

如此循环直到找不到或者完全输出.

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prerequisites int整型vector<vector<>> 
     * @param n int整型 
     * @return int整型vector
     */
    vector<int> findOrder(vector<vector<int> >& prerequisites, int n) {
        // write code here
        vector<bool> exist(n,true);// 点是否还存在
        vector<int> ans; // 入度统计
        bool found = true;
        while(found){
            found = false;
            for(int i=0;i<n;i++){ // 枚举所有点
                if(!exist[i])continue; // 已经输出到结果
                int in0 = true; // 入度为零
                for(auto item:prerequisites){ // 枚举所有边
                    if(!exist[item[1]])continue; // 入点已经输出
                    if(item[0] != i)continue;
                    in0 = false; // 入度非零
                    break;
                }
                if(in0){ // 入度为0 选取它
                    ans.push_back(i);
                    exist[i] = false;
                    found = true; // 继续搜索
                    break; // 继续搜索
                }
            }
        }
        return ans.size() == n? ans : (vector<int>());
    }
};

复杂度分析

时间复杂度: 最坏情况，每轮都是到最后才找到，所以时间复杂度为$O(n^2\cdot m)O(n^2\; \backslash cdot\; m)$

空间复杂度: 主要记录点是否存在和结果统计，所以空间复杂度为$O(n)O(n)$

按点统计

使用两个辅助数组，分别记录

1. 每个点连出的所有点
2. 每个点的入度

这样每次找到一个入度为零的点，把它的出点入度都减1，把这个点加入到输出数组中。

如果所有点都能输出，则是能够拓扑排序。

以题目样例$[[1,0],[2,1]][[1,0],[2,1]]$为例

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prerequisites int整型vector<vector<>> 
     * @param n int整型 
     * @return int整型vector
     */
    vector<int> findOrder(vector<vector<int> >& prerequisites, int n) {
        // write code here
        vector<vector<int> > p2(n,vector<int>());// 每个点的出点
        vector<int> cnt(n,0); // 每个点的入度统计
        for(auto item:prerequisites){
            p2[item[1]].push_back(item[0]); // 增加出点
            item[0]++; // 增加入度
        }
        deque<int> r0; // 入度为零的点
        vector<int> ans; // 输出结果
        for(int i = 0;i<n;i++){ // 先找已经是零的点
            if(cnt[i] == 0)
                r0.push_back(i);
        }
        while(r0.size()){ // 还有入度为零的点
            int v = r0[0]; // 取出一个入度为零的点
            r0.pop_front();
            ans.push_back(v); // 输出到结果
            for(auto item:p2[v]){ // 找依赖于这个点的点
                cnt[item] -- ; // 计数减1
                if(cnt[item] == 0) // 去除这个点后，入度变为0的点
                    r0.push_back(item);
            }
        }
        return ans.size() == n? ans : (vector<int>()); // 全部点都输出了
    }
};

复杂度分析

时间复杂度: 对于每个点是和这个点相连的边的次数的操作，对于每条边一次操作，所以时间复杂度为$O(m)O(m)$

空间复杂度: 记录了所有边和点，所以空间复杂度为$O(n+m)O(n+m)$