C++ 算法题 检测循环依赖 请你找出一个可以完成全部课程的顺序
时间: 2024-02-22 16:54:59 浏览: 13
在上一个问题中,我们已经学会了如何检测课程之间的循环依赖。如果所有课程之间不存在循环依赖,那么就可以找到一种顺序来完成所有课程的学习。具体实现代码如下:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> inDegree(numCourses, 0);
for (auto& p : prerequisites) {
int u = p[1], v = p[0];
graph[u].push_back(v);
inDegree[v]++;
}
queue<int> q;
vector<int> result;
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int node = q.front();
q.pop();
result.push_back(node);
for (int neighbor : graph[node]) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
if (result.size() != numCourses) {
return {};
}
return result;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> prerequisites(m, vector<int>(2));
for (int i = 0; i < m; i++) {
cin >> prerequisites[i][1] >> prerequisites[i][0];
}
vector<int> result = findOrder(n, prerequisites);
for (int i = 0; i < result.size(); i++) {
cout << result[i] << " ";
}
cout << endl;
return 0;
}
```
输入格式为总课程数和先决条件的数量,然后依次输入每个先决条件的前后两门课程的编号。输出结果为一种可以完成所有课程的学习顺序。如果不存在这样的顺序,则输出空序列。