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
1
3 3
1 2
2 3
3 1
Sample Output
Yes
Source
POJ Monthly--2006.02.26,zgl & twb
题目大意：给定一个有向图，判断图中任意两点u,v是否能从u到达v或从v到达u，可以的话输出Yes，不行输出No
注意这里是或者不是而且，如果是而且的话直接判断整个图是不是一个强连通分量即可，简单很多，此题的思路是先将整图缩点(每个强连通分量中任意两点均可达)，对缩点后的DAG进行拓扑排序，在排序过程中若出现多个入点为0的点则判定排序失败，若最终拓扑排序成功则表明图中任意两点u,v能从u到达v或从v到达u
#include
#include
#define MAXV 8010 #define MAXE 2010 #define cls(array,num) memset(array,num,sizeof(array)) using namespace std; struct edge { int u,v,next; }edges[MAXV],newedges[MAXV]; int head[MAXE],dfn[MAXE],low[MAXE],belong[MAXE],stack[4*MAXE],inDegree[MAXE]; bool inStack[MAXE]; int top=0,nCount=0,newCount=0,tot=0,index=0,n,m; int min(int a,int b) { if(a
1) return false; int rest=tot,result[MAXE]; while(rest--) { ans=0; for(int p=head[num];p!=-1;p=newedges[p].next) { int v=newedges[p].v; inDegree[v]--; if(inDegree[v]==0) { ans++; num=v; } } if(ans>1) return false; } return true; } int main() { int testCase; cin>>testCase; while(testCase--) { cls(head,-1); cls(dfn,0); cls(low,0); cls(stack,0); cls(inStack,0); cls(belong,0); cls(inDegree,0); top=0,nCount=0,newCount=0,tot=0,index=0; for(int i=0;i
>n>>m; for(int i=1;i<=m;i++) { int a,b; cin>>a>>b; AddEdge(a,b,edges,nCount); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); newGraph(); if(topologicalSort()) cout<<"Yes"<
??