算法模版 – 拓扑排序

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

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

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

拓扑排序的经典步骤：

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

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;
    }
};