拓扑排序

1. 统计所有节点的入度
2. 将所有入度为 0 的点加入队列
3. BFS，将与入度为 0 的点相连的节点入度减去 1，如果减到 0，该点入队

求是否存在拓扑序：

课程表

原题链接

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        vector<int> d(n);
        for(auto& e: edges) {
            int a = e[0], b = e[1];
            g[a].push_back(b);
            d[b]++;
        }

        queue<int> q;
        for(int i=0;i<n;i++) {
            if(d[i] == 0) {
                q.push(i);
            }
        }
        int cnt = 0;
        while(q.size()) {
            auto t = q.front();
            q.pop();
            cnt++;
            for(auto i: g[t]) {
                if(--d[i] == 0) {
                    q.push(i);
                }
            }
        }
        return cnt == n;
    }
};