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

1331_是否可达

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

摘要:

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

Pro.ID

1331

Title

是否可达

Title链接

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

AC

Submit

401

Ratio

14.71%

时间&空间限制

Time Limit: 40000/40000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

给出一个有向图，请判断图中某顶点a是否可到达另一顶点b 。

输入

多测试用例。每个测试用例如下：

第一行给出该有向图的顶点数 n （ 1 ≤ n ≤ 1000 ）。顶点从1开始编号。

第二行给出该有向图的边数 e （ 0 ≤ e ≤ 200000 ）。

第三行开始，共e行，每行两个正整数 a b，表示从顶点a发出一条弧到顶点b。

接下来是一个正整数T，表示有T个提问。

接下来T行，每行两个整数u v，表示提问从顶点u是否可到达顶点v。

输出

Description

给出一个有向图，请判断图中某顶点a是否可到达另一顶点b 。

Input

多测试用例。每个测试用例如下：

第一行给出该有向图的顶点数 n （ 1 ≤ n ≤ 1000 ）。顶点从1开始编号。

第二行给出该有向图的边数 e （ 0 ≤ e ≤ 200000 ）。

第三行开始，共e行，每行两个正整数 a b，表示从顶点a发出一条弧到顶点b。

接下来是一个正整数T，表示有T个提问。

接下来T行，每行两个整数u v，表示提问从顶点u是否可到达顶点v。

Output

为每个测试用例输出T行，对应每个提问，如果从顶点u可以到达顶点v，输出一行yes，否则输出no。

然后输出一个空行。

Sample Input

4
6
1 2
1 3
2 3
2 1
3 2
2 4
5
1 2
3 1
1 4
4 1
4 4

Sample Output

yes
yes
yes
no
yes

Author

John

样例输入