leetcode 207課程表

?

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {//驗證是否為DAG，每次驗證指向的是否已經存在于當前圖中//建圖vector<int> indegree(numCourses,0);//入度vector<vector<int>> graph(numCourses,vector(0,0));//鄰接表for(int i=0;i<prerequisites.size();i++){indegree[prerequisites[i][1]]++;graph[prerequisites[i][0]].push_back(prerequisites[i][1]);}//顯示圖showgraph(graph,numCourses);//BFSqueue<int> q;for(int i=0;i<numCourses;i++){if(indegree[i]==0){q.push(i);}}//將入度為0的點且未訪問過的進入set，然后將其后繼的入度全部減一，循環執行int cnt=0;while(!q.empty()){int front=q.front();q.pop();cnt++;for(int j=0;j<graph[front].size();j++){int v=graph[front][j];indegree[v]--;if(indegree[v]==0){q.push(v);}}}return cnt==numCourses;//當有環時，總有一些點入度不能減到0，因此不能完全bfs遍歷
    }
private:void showgraph(vector<vector<int>>& graph,int numCourses){for(int i=0;i<numCourses;i++){cout<<i<<": ";for(int j=0;j<graph[i].size();j++){cout<<graph[i][j]<<",";}cout<<endl;}}
};

?