207. Course Schedule

这就是一个在图中找圈的问题。 超时代码，估摸着肯定有很多的路重复走了很多次，所以下一步就是想办法减少重复路径。 超时代码：

class Solution { public: //start=0; bool BFS(vector<int>& visit,int start,vector<vector<int>>& matrix) { for(int i=0;i<matrix.size();i++) { if(matrix[start][i]==1) { if(visit[i]==1) return false; else { visit[i]=1; if(BFS(visit,i,matrix)==false) return false; visit[i]=0; } } } return true; } bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { vector<int> temp(numCourses,0); vector<vector<int>> matrix(numCourses,temp); for(int i=0;i<prerequisites.size();i++) matrix[prerequisites[i].second][prerequisites[i].first]=1; /*for(int i=0;i<numCourses;i++) { for(int j=0;j<numCourses;j++) cout<<matrix[i][j]<<" "; cout<<endl; }*/ vector<int> visit(numCourses,0); for(int start=0;start<numCourses;start++) { visit[start]=1; if(BFS(visit,start,matrix)==false) return false; visit[start]=0; } return true; } };

增加一个rightNode数组，成功AC，最终AC代码为：六次AC啊，都要哭了==

class Solution { public: //start=0; bool BFS(vector<int>& visit,vector<int>& rightNodes,int start,vector<vector<int>>& matrix) { for(int i=0;i<matrix.size();i++) { if(matrix[start][i]==1) { if(visit[i]==1) return false; else if(rightNodes[i]==1) {} else { visit[i]=1; if(BFS(visit,rightNodes,i,matrix)==false) return false; visit[i]=0; } } } rightNodes[start]=1; return true; } bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { vector<int> temp(numCourses,0); vector<vector<int>> matrix(numCourses,temp); for(int i=0;i<prerequisites.size();i++) matrix[prerequisites[i].second][prerequisites[i].first]=1; vector<int> visit(numCourses,0); vector<int> rightNodes(numCourses,0); for(int start=0;start<numCourses;start++) { if(rightNodes[start]==0) { visit[start]=1; if(BFS(visit,rightNodes,start,matrix)==false) return false; else rightNodes[start]=1; visit[start]=0; } } return true; } };