C++ 算法题 检测循环依赖 思路详解

检测循环依赖一般可以使用拓扑排序来实现。

拓扑排序是一种有向无环图（DAG）的排序方法，它可以将一个有向无环图中的所有节点排列成一个线性序列，使得对于任意一条有向边，起点在序列中都排在终点的前面。如果该有向图有环，则不能进行拓扑排序。

对于一个 C++ 项目的依赖关系，我们可以将每个文件看成一个节点，依赖关系看成有向边，然后构建一个有向无环图。如果存在循环依赖，则无法进行拓扑排序，也就无法进行编译。

具体实现步骤如下：

1. 统计每个文件的依赖关系，构建有向无环图。

2. 找到所有入度为 0 的节点，将其加入队列。

3. 从队列中取出一个节点，将其从图中删除，并将其所有后继节点的入度减 1。

4. 如果某个节点的入度变为 0，则将其加入队列。

5. 重复执行步骤 3 和 4，直到队列为空。

6. 如果图中仍然存在节点，则说明存在循环依赖。

代码实现如下：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 100;

vector<int> adj[MAXN]; // 存储有向无环图
int indegree[MAXN]; // 存储每个节点的入度
int n, m; // 节点数和边数

bool topological_sort() {
    queue<int> q;
    int cnt = 0; // 记录已经取出的节点数

    // 将所有入度为 0 的节点加入队列
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cnt++;

        // 删除节点 u，并将其所有后继节点的入度减 1
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 如果已经取出的节点数等于节点总数，则说明拓扑排序成功
    return cnt == n;
}

int main() {
    cin >> n >> m;

    // 构建有向无环图
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); // 添加一条有向边
        indegree[v]++; // 更新节点 v 的入度
    }

    if (topological_sort()) {
        cout << "No cycle detected." << endl;
    } else {
        cout << "Cycle detected." << endl;
    }

    return 0;
}