There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have PRerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]] There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
s思路： 1. 图。描述两者之间关系用edge表示，每个对象就是一个node。首先，把问题转化成图。 2. 看到图，心里就打颤，遇到的少，心里没底。也不是没底，是深不可侧，不见底。所以，需要先把心安好，既重视，更要看轻图，才能学好图。 3. 回到图。先转换图，把每门课的所有先修课程和这门课连接起来，然后做dfs遍历，看是否cycle，用dfs时，就要对每个节点是否visited做标记，而且dfs由于是recursive,和其他所有recursive一样，都有层级之分。在dfs的visited数据结构，需要有三个状态，不同与之前见过的两个状态表示是否访问。三个状态分别是：没访问，正在访问但没访问完成，以及访问完成。“正在访问但没访问完成”：表示从这个节点出发进入下一个层次去访问，此时这个点确实被访问了，但是这个点属于现在正在访问的path的一个节点；“访问完成”表示当前点的下一个层次的遍历以及完成，注意，下一个层次包括所有邻接节点都访问了，这个点才算访问完。 4. 写完dfs,发现图的dfs的套路和backtracking一毛一样，都是for+recursive。不同的就是，visited有3中状态！ 5. 按理说，能用dfs的也可以用bfs，只要能想办法添加一些辅助量。图的bfs和其他的bfs一样，也是一层访问完再访问下一层，而且也用到queue。如果说dfs检查是否有cycle这个操作就可以表面是否所有课都可以选，那么bfs需要做什么呢？看了答案，很有意思，仍然是检查是否有cycle,但需利用图论的知识：对每个节点的入度(indegree)统计，然后找到入度为0的所有点放在queue里，每次取出一个点，找到和其相连的所有节点，然后把这些节点的入度减一，表示删除这条边，如果某一次删除，导致入度变成0，那么就把这个点加入queue,最后等queue为空后，再看所有点的入度是否全为0，如果全为0表示没有cycle，否则有cycle。 6. 数学原因先不说。单说思路，仍然是找到边界这个方法的应用。先统计所有入度，从入度为0的点入手，这里入度为0的点就是边界。形象的说，一个图的入读为0的点在图上也一定是在边缘，只出不进，所以是边缘。值得注意的是，如果没有入度为0的点，说明这个图的所有点都在loop内；然后删除和这个点相连的节点之间的连接，同时入度减一，如果没有cycle，最后一定可以把所有所有的入度变成0。所以，根据这个条件，就可以判断是否有cycle了！ 7. 比较一下dfs和bfs区别:dfs的过程是在模拟如何去遍历这个图的全过程；bfs则是模拟如何从图的边缘一步一步的把图给“拆”掉，如果把能拆的都拆了，发现还有连线，那就是有cycle。一个是在沿路走；一个是在把正常的路拆了看留下啥！
//方法1：recursive. dfs，使用visited表示已经访问。class Solution {public: bool dfs(vector<vector<int>>&graph,vector<int>&visited,int i){ //dfs:这个和backtracking套路一样 if(visited[i]==2) return true;//完全访问过 if(visited[i]==1) return false;//正在访问，所以再次遇到表示有cycle visited[i]=1;//第一次访问，所以置为1 for(int j=0;j<graph[i].size();j++){ if(!dfs(graph,visited,graph[i][j])) return false; } visited[i]=2; return true; } bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { // vector<vector<int>> graph(numCourses); vector<int> visited(numCourses,0); //step 1: build graph for(auto p:prerequisites){ graph[p.first].push_back(p.second); } //step 2: dfs找cycle for(int i=0;i<numCourses;i++){ if(!dfs(graph,visited,i)) return false; } return true; }};//方法2：iterative,queue,统计入度class Solution {public: bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { // vector<vector<int>> graph(numCourses); vector<int> indegree(numCourses,0); queue<int> QQ; //step 1: build graph for(auto p:prerequisites){ graph[p.first].push_back(p.second); indegree[p.second]++; } //step 2:找图边缘入度为0的点放入queue for(int i=0;i<numCourses;i++){ if(indegree[i]==0) qq.push(i); } //step 3:拆掉和入度零连接的线，入度减少 while(!qq.empty()){ int cur=qq.front(); qq.pop(); for(auto k:graph[cur]){ indegree[k]--; if(indegree[k]==0) qq.push(k); } } //step 4：看是否入度都为0 for(int i=0;i<numCourses;i++){ if(indegree[i]!=0) return false; } return true; }};新闻热点
疑难解答
