1 // 将先修关系构成一张图,由每个数对的第二个数字向第一个数字连边。 2 // 首先将所有入度为0的点进队,准备拓扑排序。 3 // 宽搜过程中,将当前结点所关联的结点的入度减1;若发现新的入度为0的结点,则将其进队。 4 // 最后如果遍历了所有结点,则说明可以满足要求;否则,先修关系存在环。 5 6 //查找是否有环 7 class Solution 8 { 9 public: 10 bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 11 { 12 vector<vector<int>> graph(numCourses); 13 vector<int> in_degree(numCourses, 0); 14 for (int i = 0; i < prerequisites.size(); i++) 15 { 16 in_degree[prerequisites[i][0]]++; 17 graph[prerequisites[i][1]].push_back(prerequisites[i][0]); 18 } 19 20 queue<int> q; 21 vector<bool> vis(numCourses, false); 22 23 for (int i = 0; i < numCourses; i++) 24 if (in_degree[i] == 0) 25 q.push(i); 26 while (!q.empty()) 27 { 28 int sta = q.front(); 29 q.pop(); 30 vis[sta] = true; 31 //有哪些邻边 32 for (int i = 0; i < graph[sta].size(); i++) 33 { 34 in_degree[graph[sta][i]]--;// 入度-1 35 if (in_degree[graph[sta][i]] == 0) //入度如果为0,加入队列 36 q.push(graph[sta][i]); 37 } 38 } 39 40 //0->1->2 41 for (int i = 0; i < numCourses; i++) 42 if (vis[i] == false) 43 return false;//有环 44 return true;//无环 45 } 46 };