Pro.ID1569 Titlehow many path Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1569 AC10 Submit33 Ratio30.30% 时间&空间限制描述Given an directed graph G = (V, E), and two vertices u, v ∈ V, you are asked to determine how many deferent 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 arc <a, b> ∈ E. 输出Description Given an directed graph G = (V, E), and two vertices u, v ∈ V, you are asked to determine how many deferent 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 arc <a, b> ∈ E. Output For each case, output the number of different path from a to b . Sample Input 2 Sample Output 2 Author 样例输入2 样例输出2 提示作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2024-9-21 00:37 , Processed in 0.013882 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
