C++ 算法题 检测循环依赖 选课依赖

假设现在有 n 门课程，它们的编号分别为 0 到 n-1。有些课程需要先修另外一门课程才能学习，例如若想学习课程 0，需要先学习课程 1，表示为 [0,1]。

给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习。

例如，输入 2，[[1,0]]，表示想学习两门课程，其中需要先学习课程 1 才能学习课程 0。则输出 true，因为可以先学习课程 1，再学习课程 0。

检测循环依赖的方法和上面的算法题相同，具体实现代码如下：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool canFinish(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;
    int cnt = 0;
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cnt++;
        for (int neighbor : graph[node]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }
    return cnt == numCourses;
}

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];
    }
    bool result = canFinish(n, prerequisites);
    cout << (result ? "true" : "false") << endl;
    return 0;
}

输入格式为总课程数和先决条件的数量，然后依次输入每个先决条件的前后两门课程的编号。输出结果为 "true" 或 "false"，表示是否能够完成所有课程的学习。