算法模版 – 拓扑排序

课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

在无向图中判断是否存在环，则使用并查集。

在有向图中判断是否存在环，则可以使用拓扑排序。

拓扑排序的原理是使用队列维护一个入度为0的队列，当最后队列中不存在元素时，拓扑序列的长度如果等于全图节点数，则无环，否则即存在环。

拓扑排序的经典步骤：

• 1 先得到图中每一个节点的入度。
• 2 将入度为0的节点加入队列。
• 3 从队列中弹出一个元素，加入拓扑序列中，同时删除该元素的出边。
• 4 判断出边的节点的入度是否为0，是则加入队列
• 5 重复3-4步骤，直到队列中元素为0

需要的数据结构：

• 1 入度数组
• 2 拓扑序列
• 3 邻接矩阵

class Solution {
public:
    bool canFinish(int numCourses, vector<vector>& prerequisites) {
        int m = prerequisites.size();
        if (m==0) return true;
        vector din(numCourses, 0);
        vector<vector> adj(numCourses);
        queue que;
        // 1 先得到每一个节点的入度
        for(int i=0; i<m; i++)
        {
            din[prerequisites[i][0]]++;
            adj[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }
        // 2 将入度为0的节点加入队列
        for(int i=0; i<numCourses; i++)
        {
            if (din[i] == 0) que.push(i);
        }
        // 3 出队列的节点的边删除
        while(que.size())
        {
            // 4 出队
            int x = que.front(); que.pop();
            numCourses--;
            // 5 入队
            for(auto y:adj[x]){
                if(--din[y] == 0) que.push(y);
            }
        }
        return numCourses==0;
    }
};