C语言运行【题目描述】给定无权有向图G(V,E)，请判断G是否是一个有向无环图（DAG）。 【输入格式】 第一行包含两个整数N、M，表示该图共有N个结点和M条有向边。（N <= 5000，M <= 200000） 接下来M行，每行包含2个整数{u,v}，表示有一条有向边(u,v) 【输出格式】 有环输出“not DAG”，无环输出“DAG” 【输入样例】 5 7 1 2 1 5 2 3 3 1 3 2 4 1 4 5 【输出样例】 not DAG not DAG

以下是 C 语言的代码实现，使用邻接表存储图，并实现了拓扑排序判断 DAG：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 5000
#define MAXM 200000

typedef struct Node {
    int val;
    struct Node *next;
} Node;

int N, M;
Node *graph[MAXN + 1];  // 邻接表存储图
int indegree[MAXN + 1]; // 存储每个节点的入度

void add_edge(int u, int v) {
    Node *p = (Node *) malloc(sizeof(Node));
    p->val = v;
    p->next = graph[u];
    graph[u] = p;
}

void topo_sort() {
    int q[MAXN];
    int front = 0, rear = -1;
    for (int i = 1; i <= N; i++) {
        if (indegree[i] == 0) {
            q[++rear] = i;
        }
    }
    while (front <= rear) {
        int u = q[front++];
        Node *p = graph[u];
        while (p) {
            int v = p->val;
            indegree[v]--;
            if (indegree[v] == 0) {
                q[++rear] = v;
            }
            p = p->next;
        }
    }
    if (front <= N) {
        printf("not DAG\n");
    } else {
        printf("DAG\n");
    }
}

int main() {
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        indegree[v]++;
    }
    topo_sort();
    return 0;
}