#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;/*给定一个有向图，求：1) 至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点DAG上入度为0的点个数2) 至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点DAG上max(入度为0的点数,出度为0的点数）；n=1时单独考虑*/const int maxn=100000;struct edge{ int t,w;//u->t=w; int next;};int V,E;//点数(从1开始)，边数int p[maxn],pf[maxn];//邻接表原图,逆图edge G[maxn],Gf[maxn];//邻接表原图,逆图int l,lf;void init(){ memset(p,-1,sizeof(p)); memset(pf,-1,sizeof(pf)); l=lf=0;}void addedge(int u,int t,int w,int l){ G[l].w=w; G[l].t=t; G[l].next=p[u]; p[u]=l;}void addedgef(int u,int t,int w,int l){ Gf[l].w=w; Gf[l].t=t; Gf[l].next=pf[u]; pf[u]=l;}///Kosaraju算法,返回为强连通分量个数bool flag[maxn]; //访问标志数组int belg[maxn]; //存储强连通分量,其中belg[i]表示顶点i属于第belg[i]个强连通分量int numb[maxn]; //结束时间(出栈顺序)标记,其中numb[i]表示离开时间为i的顶点//用于第一次深搜,求得numb[1..n]的值void VisitOne(int cur, int &sig){ flag[cur] = true; for (int i=p[cur];i!=-1;i=G[i].next) { if (!flag[G[i].t]) { VisitOne(G[i].t,sig); } } numb[++sig] = cur;}//用于第二次深搜,求得belg[1..n]的值void VisitTwo(int cur, int sig){ flag[cur] = true; belg[cur] = sig; for (int i=pf[cur];i!=-1;i=Gf[i].next) { if (!flag[Gf[i].t]) { VisitTwo(Gf[i].t,sig); } }}//Kosaraju算法,返回为强连通分量个数int Kosaraju_StronglyConnectedComponent(){ int i, sig; //第一次深搜 memset(flag,0,sizeof(flag)); for ( sig=0,i=1; i<=V; ++i ) { if ( false==flag[i] ) { VisitOne(i,sig); } } //第二次深搜 memset(flag,0,sizeof(flag)); for ( sig=0,i=V; i>0; --i ) { if ( false==flag[numb[i]] ) { VisitTwo(numb[i],++sig); } } return sig;}//缩点int n;//缩点后的点个数1~nint g[maxn];edge eg[maxn];//邻接表int re;int in[maxn];//入度int mat[1100][1100];//DAG的邻接矩阵void dinit(int sig){ memset(g,-1,sizeof(g)); n=sig; re=0; memset(mat,0,sizeof(mat)); memset(in,0,sizeof(in));}void addedge0(int u,int t,int w,int l){ eg[l].w=w; eg[l].t=t; eg[l].next=g[u]; g[u]=l;}int topo[maxn];int ct;bool toposort()//缩点后拓扑排序肯定不存在环{ ct=0; int top=-1; for(int i=1;i<=n;i++) { if(in[i]==0) in[i]=top,top=i; } for(int l=1;l<=n;l++) { int cur=top; //if(top==-1) return 0; top=in[top]; topo[ct++]=cur; for(int i=g[cur];i!=-1;i=eg[i].next) { in[eg[i].t]--; if(in[eg[i].t]==0) in[eg[i].t]=top,top=eg[i].t; } } return 1;}int main(){ int ci;scanf("%d",&ci); while(ci--) { init(); scanf("%d%d",&V,&E); for(int i=1;i<=E;i++) { int u,t,w=1;scanf("%d%d",&u,&t); addedge(u,t,w,l++); addedgef(t,u,w,lf++); } int ans=Kosaraju_StronglyConnectedComponent(); //printf("%d/n",ans); ///缩点 dinit(ans); for(int i=1;i<=V;i++)//构图 { for(int j=p[i];j!=-1;j=G[j].next) { int st=belg[i],ed=belg[G[j].t]; if(st!=ed) { int flag=1; for(int k=g[st];k!=-1;k=eg[k].next) { if(eg[k].t==ed) { flag=0; break; } } if(flag) { addedge0(st,ed,1,re++); mat[st][ed]=1; in[ed]++; } } } } //拓扑排序 如果拓扑序中任意第i个和第i+1个有边相连 则YES 否则NO toposort(); int flag=1; for(int i=0;i<ct-1;i++) { int u=topo[i],v=topo[i+1]; if(!mat[u][v]) { flag=0; break; } } if(flag) printf("Yes/n"); else printf("No/n"); } return 0;}
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 1Sample Output
YesDescription
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 1Sample Output
YesDescription
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 1Sample Output
Yes