c++判定有向无环图两种方法 输出两次

第一种方法是使用拓扑排序，将有向无环图中的节点按照依赖关系进行排序，如果成功进行拓扑排序，说明图是有向无环图；否则，说明图中存在环。

C++代码实现如下：

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

using namespace std;

bool isDAG(int n, vector<vector<int>>& graph) {
    vector<int> inDegree(n, 0);
    for (vector<int>& edge : graph) {
        for (int v : edge) {
            inDegree[v]++;
        }
    }

    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    int cnt = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cnt++;
        for (int v : graph[u]) {
            if (--inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    return cnt == n;
}

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

    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    if (isDAG(n, graph)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

第二种方法是使用深度优先搜索（DFS），对每个节点进行访问，并且记录每个节点的状态（未访问、正在访问、已访问）。如果存在正在访问的节点，则说明图中存在环。

C++代码实现如下：

#include <iostream>
#include <vector>

using namespace std;

bool dfs(int u, vector<vector<int>>& graph, vector<int>& state) {
    if (state[u] == 1) {
        return false;
    }
    if (state[u] == 2) {
        return true;
    }

    state[u] = 1;
    for (int v : graph[u]) {
        if (!dfs(v, graph, state)) {
            return false;
        }
    }
    state[u] = 2;

    return true;
}

bool isDAG(int n, vector<vector<int>>& graph) {
    vector<int> state(n, 0);
    for (int i = 0; i < n; i++) {
        if (!dfs(i, graph, state)) {
            return false;
        }
    }
    return true;
}

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

    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    if (isDAG(n, graph)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

以上两种方法都可以判断有向无环图，具体实现可以根据实际情况进行选择。