- class Solution
- {
- vector<int> res;
- public:
- vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)
- {
- vector<vector<int>> graph(numCourses);
- vector<int> in_degree(numCourses, 0);
- for (int i = 0; i <prerequisites.size(); i++)
- {
- in_degree[prerequisites[i][0]]++;
- graph[prerequisites[i][1]].push_back(prerequisites[i][0]);
- }
- queue<int> q;
- vector<bool> vis(numCourses, false);
- for (int i = 0; i <numCourses; i++)
- if (in_degree[i] == 0)
- q.push(i);
- while (!q.empty())
- {
- int sta = q.front();
- q.pop();
- vis[sta] = true;
- res.push_back(sta);
- // 有哪些邻边
- for (int i = 0; i < graph[sta].size(); i++)
- {
- in_degree[graph[sta][i]]--;// 入度 - 1
- if (in_degree[graph[sta][i]] == 0) // 入度如果为 0, 加入队列
- q.push(graph[sta][i]);
- }
- }
- //0->1->2
- for (int i = 0; i < numCourses; i++)
- if (vis[i] == false)// 只要有 false, 则返回 {}
- return {};// 有环
- return res;
- }
- };
来源: http://www.bubuko.com/infodetail-3491813.html