讨论/《广度优先搜索》 - 「力扣」第 1136 题:平行课程(困难)/
《广度优先搜索》 - 「力扣」第 1136 题:平行课程(困难)
共 1 个回复
//-----1.BFS 拓扑排序
//结点编号从1开始,1~n
class Solution {
public:
    int minimumSemesters(int n, vector<vector<int>>& relations) {
        //1.初始化邻接表
        vector<unordered_set<int>> adj(n+1); //n+1个集合,只使用第1~n个
        vector<int> inDegree(n+1,0);
        for(vector<int>& rel:relations){
            inDegree[rel[1]]++;
            adj[rel[0]].insert(rel[1]);
        }
        //2.广搜
        queue<int> Q;
        for(int i=1;i<=n;i++){ //把入度为0的节点入队。入度为 0 的所有顶点在拓扑排序的结果中位于其它顶点的前面
            if(inDegree[i]==0){
                Q.push(i);
            }
        }
        int step=0; //层数
        while(!Q.empty()){ 
            int size=Q.size();
            for(int i=0;i<size;i++){ //逐层剥洋葱,一次遍历一层结点
                int cur=Q.front();
                Q.pop();
                unordered_set<int> cur_set=adj[cur];
                for(int cur_adj:cur_set){
                     // 删除一条边,等价于被指向结点的入度减 1
                    inDegree[cur_adj]--;
                    if(inDegree[cur_adj]==0){ //没必要真的去删除结点,只需把入度为0的节点入队等待减小以它为起点的那些结点的入度即可
                        Q.push(cur_adj);
                    }
                }
                
            }
            step++;
        }
        //3.剥完洋葱后,若还有一些顶点有边指向它,说明图中存在环
        for(int i=1;i<=n;i++){
            if(inDegree[i]!=0){
                return -1;
            }
        }
        return step;
    }
};