Going from u to v or from v to u?
Time Limit: 2000MS | | Memory Limit: 65536K |
Total Submissions: 16486 | | Accepted: 4386 |
Description
In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn't know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything?
Input
The first line contains a single integer T, the number of test cases. And followed T cases.
The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly.
Output
The output should contain T lines. Write 'Yes' if the cave has the property stated above, or 'No' otherwise.
Sample Input
13 31 22 33 1
Sample Output
Yes
有一张有向图,然后问对于任意的2个点,是否存在x可以到达y,或者y能够到达x。
可以先强连通缩点,这样就没有环的情况。然后这样就是一张新的图。也就是相当于在新的图中判断任意2个点能否存在一条路径。这可以用topo排序来解决。如果存在2个点,他们的入度为0,说明这2个点是不能相互到达的。
/* * Author: sweat123 * Created Time: 2016/6/25 12:33:09 * File Name: main.cpp */#include #include