有向图判断是否有回路的代码

以下是使用深度优先遍历（DFS）判断有向图是否有回路的代码示例：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

bool dfs(int node, vector<vector<int>>& graph, vector<bool>& visited, vector<bool>& recursion) {
    visited[node] = true;
    recursion[node] = true;

    for (int i = 0; i < graph[node].size(); i++) {
        int neighbor = graph[node][i];
        if (!visited[neighbor]) {
            if (dfs(neighbor, graph, visited, recursion)) {
                return true;
            }
        } else if (recursion[neighbor]) {
            return true;
        }
    }

    recursion[node] = false;
    return false;
}

bool hasCycle(vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    vector<bool> recursion(graph.size(), false);

    for (int i = 0; i < graph.size(); i++) {
        if (!visited[i]) {
            if (dfs(i, graph, visited, recursion)) {
                return true;
            }
        }
    }

    return false;
}

int main() {
    vector<vector<int>> graph = {{1, 2}, {2, 3}, {3, 1}, {4, 5}, {5, 6}, {6, 4}};
    if (hasCycle(graph)) {
        cout << "The graph has a cycle" << endl;
    } else {
        cout << "The graph does not have a cycle" << endl;
    }
    return 0;
}

上述代码使用了一个 `visited` 数组来记录已经访问过的节点，以及一个 `recursion` 数组来记录当前节点是否已经在递归中被访问过。在每次遍历到一个新节点时，首先将其标记为已访问，并将其标记为正在递归中。然后遍历其所有邻居节点，如果邻居节点还没有被访问过，则继续递归遍历邻居节点；如果邻居节点已经被访问过但还在递归中，则说明存在回路，返回 `true`。如果遍历完所有节点后都没有发现回路，则返回 `false`。