Pro.ID1568 TitleConnectivity Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1568 AC25 Submit60 Ratio41.67% 时间&空间限制描述Given an undirected graph G = (V, E), and two vertices u, v ∈ V, you are asked to determine whether there is a path between u and v. 输入The input begins with a line containing an integer T (T ≤ 500), which indicates the number of test cases. Each case begins with four integers N, M, u and v (2 ≤ N ≤ 10000, 0 ≤ M ≤ 100000, 1 ≤ u, v ≤ N, u ≠ v). The following M lines each consist of two integers a and b (1 ≤ a, b ≤ N, a ≠ b), indicating that edge (a, b) ∈ E. 输出Description Given an undirected graph G = (V, E), and two vertices u, v ∈ V, you are asked to determine whether there is a path between u and v. Input The input begins with a line containing an integer T (T ≤ 500), which indicates the number of test cases. Each case begins with four integers N, M, u and v (2 ≤ N ≤ 10000, 0 ≤ M ≤ 100000, 1 ≤ u, v ≤ N, u ≠ v). The following M lines each consist of two integers a and b (1 ≤ a, b ≤ N, a ≠ b), indicating that edge (a, b) ∈ E. Output For each case, output YES if there is a path between a and b; otherwise output NO . Sample Input 2 Sample Output YES Author 样例输入2 样例输出YES 提示作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2024-9-21 00:37 , Processed in 0.015559 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
