C++代码有向无环图的判定DFS

以下是C++实现有向无环图的判定的DFS代码：

#include <iostream>
#include <vector>

using namespace std;

vector<int> adj[100001];
bool visited[100001];
bool on_stack[100001];

bool dfs(int node) {
    visited[node] = true;
    on_stack[node] = true;

    for (int i = 0; i < adj[node].size(); i++) {
        int neighbor = adj[node][i];

        if (!visited[neighbor]) {
            if (dfs(neighbor)) {
                return true;
            }
        } else if (on_stack[neighbor]) {
            return true;
        }
    }

    on_stack[node] = false;
    return false;
}

bool isDAG(int n) {
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            if (dfs(i)) {
                return false;
            }
        }
    }

    return true;
}

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

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        adj[a].push_back(b);
    }

    if (isDAG(n)) {
        cout << "Given graph is a DAG\n";
    } else {
        cout << "Given graph is not a DAG\n";
    }

    return 0;
}

其中，`adj`数组表示有向图的邻接表，`visited`数组表示节点是否被访问过，`on_stack`数组表示节点是否在当前搜索路径上。`dfs`函数为深度优先搜索函数，其中使用了递归的方式进行搜索，并且使用了`on_stack`数组判断是否存在环。`isDAG`函数为判断有向无环图的函数，其中对所有未访问过的节点进行深度优先搜索，并判断是否存在环，如果存在环则不是有向无环图，否则是有向无环图。