OpenJudge

E07P03:有向图无环(DAG)的判定

总时间限制:
1000ms
内存限制:
65536kB
描述

给定无权有向图G(V,E),请判断G是否是一个有向无环图(DAG)。

*在有向图中,若存在B边,则存在环。

输入
第一行包含两个整数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
全局题号
15294
添加于
2017-07-28
提交次数
20
尝试人数
10
通过人数
10