poj2762

maksyuki 发表于 oj 分类,标签: ,
0

Going from u to v or from v to u?

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

1

3 3

1 2

2 3

3 1

Sample Output

Yes

Source

POJ Monthly--2006.02.26,zgl & twb

 

题目类型:有向图强连通分量(Tarjan) +缩点+拓扑排序判定

算法分析:这个题目要判断一个图是否是单连通的,由于图中同一个强连通分量中的点一定是单连通的,所以可以不用考虑同一个强连通分量中的所有点之间的连通情况继而将其缩成一个点。然后考察缩完点之后的图,易知这个图任意两点之间最多单向可达。由于处理后得到的图仍然是有向图,所以可以对图进行拓扑排序。对于得到的拓扑序列,相邻的节点要么是”非同层”顶点,要么是”同层”顶点(拓扑排序过程中某次入度为0的顶点之间互为”同层”顶点)。对于以上两种情况,只要满足拓扑序中所有相邻的顶点之间邻接,则由传递性可知,每个顶点之间都可达