拓扑排序裸题

拓扑排序不仅要存储图，还要存储每个点入度和拓扑排序的结果数组。

1. 将所有入度为0的点入队
2. 普通bfs过程，对头弹出点t，遍历连接的所有点，对于每个连接的点j入度-1，若j点入度为0了，则该点入队并且加入拓扑排序的结果数组

时间复杂度$O(N + M)$，空间复杂度$O(N)$

AC代码

class Solution {
public:
    static const int N = 1e5 + 10;

    int h[N], e[N], ne[N], idx;//邻接表
    int de[N];//记录每个点的入度
    int top[N], k;//记录top排序的结果
    int n, m;

    void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }

    bool topSort(){
        queue<int> q;
        //讲所有入度为0的点入队
        for (int i = 0 ; i < n ; i ++){
            if (de[i] == 0){
                q.push(i);
                top[k ++] = i;
            }
        }

        while (q.size()){
            auto t = q.front();
            q.pop();
            for (int p = h[t] ; p != -1 ; p = ne[p]){
                int j = e[p];
                //入度--
                de[j] -- ;//t->j
                //删去后如果j的入度为0了，则可以入队
                if (de[j] == 0){
                    q.push(j);
                    top[k ++] = j;
                }
            }
        }
        //判断所有元素是否都入过队
        if (n == k) return true;
        else return false;
    }


    bool canFinish(int numCourses, vector<vector<int>>& pre) {
        n = numCourses;
        m = pre.size();
        memset(h , -1, sizeof h);
        //建图
        for (int i = 0 ; i < pre.size() ; i ++){
            int a = pre[i][0], b = pre[i][1];
            de[b] ++;
            add(a, b);
        }
        //拓扑排序
        return topSort();
    }
};