用c++代码利用两中方法解决给定无权有向图G(V,E)，请判断G是否是一个有向无环图（DAG）。 【输入格式】 第一行包含两个整数N、M，表示该图共有N个结点和M条有向边。（N <= 5000，M <= 200000） 接下来M行，每行包含2个整数{u,v}，表示有一条有向边(u,v) 【输出格式】 有环输出“not DAG”，无环输出“DAG”

方法一：拓扑排序

拓扑排序的思想是，将有向图中的节点按照依赖关系排序，使得每个节点都在其依赖的节点之后。如果有环，则必然存在某个节点无法找到入度为0的节点，无法进行拓扑排序。

以下是使用拓扑排序判断有向图是否为DAG的代码实现：

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

using namespace std;

const int MAXN = 5005;

vector<int> adj[MAXN];
int indeg[MAXN];

bool topoSort(int n) {
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) {
            q.push(i);
        }
    }
    int cnt = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cnt++;
        for (int v : adj[u]) {
            indeg[v]--;
            if (indeg[v] == 0) {
                q.push(v);
            }
        }
    }
    return cnt == n;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        indeg[v]++;
    }
    if (topoSort(n)) {
        cout << "DAG" << endl;
    } else {
        cout << "not DAG" << endl;
    }
    return 0;
}

方法二：DFS判断有向环

使用DFS判断有向图是否为DAG的思路是，对于每个节点，先标记为正在访问中，然后遍历其邻居节点。如果邻居节点已经被访问过，但还没有被标记为已完成访问，则说明存在环。

以下是使用DFS判断有向图是否为DAG的代码实现：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 5005;

vector<int> adj[MAXN];
int vis[MAXN];

bool dfs(int u) {
    vis[u] = 1;
    for (int v : adj[u]) {
        if (vis[v] == 1) {
            return false;
        } else if (vis[v] == 0) {
            if (!dfs(v)) {
                return false;
            }
        }
    }
    vis[u] = 2;
    return true;
}

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

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    if (isDAG(n)) {
        cout << "DAG" << endl;
    } else {
        cout << "not DAG" << endl;
    }
    return 0;
}

两种方法的时间复杂度都为 $O(N+M)$。