同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1393_判断给定图是否存在合法拓扑序列

2022-5-16 18:17| 发布者: Hocassian| 查看: 37| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-89503849804100-Problem List-采集的数据-后羿采集器.html

Pro.ID

1393

Title

判断给定图是否存在合法拓扑序列

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1393

AC

Submit

122

Ratio

34.43%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

描述

给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。

输入

多测试用例。

每个测试用例的第一行是两个正整数n, e，表示该有向图有n个顶点数和e条边数。（ n ≤ 100 ）

下面e行，每行两个整数a, b，表示从a到b有一条有向边。

输出

Description

给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。

Input

多测试用例。

每个测试用例的第一行是两个正整数n, e，表示该有向图有n个顶点数和e条边数。（ n ≤ 100 ）

下面e行，每行两个整数a, b，表示从a到b有一条有向边。

Output

若该有向图存在合法的拓扑序列，则输出 YES，否则输出 NO

Sample Input

1 0
2 2
1 2
2 1

Sample Output

YES
NO

Author

John

样例输入