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數據結構，需要有三個狀態，不同與之前見過的兩個狀態表示是否訪問。三個狀態分別是：沒訪問，正在訪問但沒訪問完成，以及訪問完成?！罢谠L問但沒訪問完成”：表示從這個節點出發進入下一個層次去訪問，此時這個點確實被訪問了，但是這個點屬于現在正在訪問的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; }};新聞熱點
疑難解答
