[leetcode]图算法之拓扑排序/有向图判环Course Schedule

妖狐艹你老母 2021-09-28 14:32 384阅读 0赞

### 图算法之拓扑排序/有向图判环Course Schedule ###

*  题目
 *  思考
 *  代码
 *  注意

# 题目 #

[leetcode题目入口][leetcode]

# 思考 #

这道题考查了 拓扑排序+有向图判环的问题。

关键是：判断入度为0的点，并逐个删去

# 代码 #

class Solution { 
    public:
        vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) { 
            // vector<vector<int>> gr(numCourses,vector<int>());
            vector<vector<int>> graph(numCourses,vector<int>());
            vector<int> res;
            vector<int> in(numCourses,0); //入度
            res.clear();
            
            
            //构造图
            for(vector<int>& pre:prerequisites){ 
                graph[pre[1]].push_back(pre[0]);
                in[pre[0]]++;
            }
            
            queue<int> q;//存储入度为0的点
            while(!q.empty()){ 
                q.pop();
            }
            
            for(int i=0;i<numCourses;i++){ 
                if(in[i]==0){ 
                    q.push(i);
                }
            }
            
            while(!q.empty()){ 
                int front=q.front();
                q.pop();
                res.push_back(front);
                
                for(int i:graph[front]){ 
                    in[i]--;
                    if(in[i]==0){ 
                        q.push(i);
                    }
                }
            }
            
            if(res.size()!=numCourses) res.clear();
            return res;
            
        }
    };

# 注意 #

`for(vector<int>& pre:prerequisites)` &是一定要加的，否则相当于每次都重新拷贝，  
这样非常耗时

[leetcode]: https://leetcode.com/problems/course-schedule-ii/