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

方法一：拓扑排序

拓扑排序是判断一个图是否是 DAG 的常用方法。其基本思想是将 DAG 中的节点按照一定的顺序排列，使得每一条边的起点在排列中都在其终点的前面。

具体实现过程可以使用队列或栈来实现，这里使用队列实现。

代码如下：

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

using namespace std;

const int N = 5010, M = 200010;

int n, m;
int h[N], e[M], ne[M], idx;
int d[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool topsort() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!d[i]) q.push(i);

    int cnt = 0;
    while (q.size()) {
        int t = q.front(); q.pop();
        cnt ++;

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (-- d[j] == 0) q.push(j);
        }
    }

    return cnt == n;
}

int main() {
    memset(h, -1, sizeof h);

    cin >> n >> m;
    while (m -- ) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] ++;
    }

    if (topsort()) puts("DAG");
    else puts("not DAG");

    return 0;
}

方法二：DFS

另一种判断 DAG 的方法是 DFS，其基本思想是在 DFS 的过程中，如果遇到了已经被访问过的节点，则说明图中存在环，否则图是 DAG。

代码如下：

#include <iostream>
#include <vector>

using namespace std;

const int N = 5010, M = 200010;

int n, m;
int h[N], e[M], ne[M], idx;
bool st[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool dfs(int u) {
    st[u] = true;

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (st[j]) return true;
        else if (dfs(j)) return true;
    }

    st[u] = false;

    return false;
}

bool check() {
    for (int i = 1; i <= n; i++)
        if (!st[i] && dfs(i)) return false;

    return true;
}

int main() {
    memset(h, -1, sizeof h);

    cin >> n >> m;
    while (m -- ) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    if (check()) puts("DAG");
    else puts("not DAG");

    return 0;
}