算法

(拓扑排序) $O(V+E)$

一个合法的选课序列就是一个拓扑序，拓扑序是指一个满足有向图上，不存在一条边出节点在入节点后的线性序列，如果有向图中有环，就不存在拓扑序。可以通过拓扑排序算法来得到拓扑序，以及判断是否存在环。

拓扑排序步骤：

1. 建图并记录所有节点的入度。
2. 将所有入度为0的节点加入队列。
3. 取出队首的元素now，将其加入拓扑序列。
4. 访问所有now的邻接点nxt，将nxt的入度减1，当减到0后，将nxt加入队列。
5. 重复步骤3、4，直到队列为空。
6. 如果拓扑序列个数等于节点数，代表该有向图无环，且存在拓扑序。

C++ 代码

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> inDegree(numCourses);

        // 建图
        for (auto edge : prerequisites) {
            graph[edge[1]].push_back(edge[0]);
            inDegree[edge[0]]++;
        }

        int numChoose = 0;
        queue<int> q;

        // 将入度为 0 的编号加入队列
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        while (not q.empty()) {
            int nowPos = q.front();
            q.pop();
            numChoose++;
            // 将每条边删去，如果入度降为 0，再加入队列
            for (int nextPos: graph[nowPos]) {
                inDegree[nextPos]--;
                if (inDegree[nextPos] == 0) {
                    q.push(nextPos);
                }
            }
        }

        return numChoose == numCourses;
    }
};