【题目描述】给定无权有向图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
时间: 2024-02-15 17:01:51 浏览: 25
以下是该题的Python3代码实现:
```python
from collections import defaultdict
def is_DAG(n, m, edges):
# 初始化入度表和邻接表
in_degree = [0] * n
adj_list = defaultdict(list)
for u, v in edges:
in_degree[v-1] += 1
adj_list[u-1].append(v-1)
# 使用BFS拓扑排序判断是否为DAG
queue = [i for i in range(n) if in_degree[i] == 0]
count = 0
while queue:
u = queue.pop(0)
count += 1
for v in adj_list[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
return "DAG" if count == n else "not DAG"
# 读入数据
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for i in range(m)]
# 输出结果
print(is_DAG(n, m, edges))
```
算法思路:
- 先根据输入的边列表构建每个点的入度表和邻接表;
- 使用BFS拓扑排序遍历每个点,如果某个点的入度为0,则将其加入队列中;
- 每当从队列中弹出一个点时,就遍历其所有的后继节点,并将其入度减1;如果某个点的入度变为0,则将其加入队列中;
- 最终统计遍历的点数count,如果count等于总点数n,则说明图是DAG,否则不是DAG。