Going from u to v or from v to u?
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 13040 | Accepted: 3383 |
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.
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
这题要注意,边是单向边,先用强连通分量缩点,建图,再拓扑排序若是单向链刚对,否刚为错就可以a了!
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 1051
#define E 30000
#define M 1000000
using namespace std;
int head[N],head2[N],next2[E],vec2[E],sta[M],re,ans,next[E],id[N],in[N],vec[E],vis[N],dfn[N],low[N],clock_m,edge_m,edge_m2;
int addedge(int s,int e){
vec[edge_m]=e;next[edge_m]=head[s];head[s]=edge_m++;
}
int addedge2(int s,int e){
vec2[edge_m2]=e;next2[edge_m2]=head2[s];head2[s]=edge_m2++;
}
int init(){
memset(vis,0,sizeof(vis));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(head,-1,sizeof(head));
memset(head2,-1,sizeof(head2));
memset(id,0,sizeof(id));
memset(in,0,sizeof(in));
edge_m=0;clock_m=0;ans=0;re=0;edge_m2=0;
}
int tarjan(int x){
dfn[x]=low[x]=++clock_m;
sta[++ans]=x;
vis[x]=1;
for(int i=head[x];i!=-1;i=next[i]){
int goal=vec[i];
if(!dfn[goal]){
tarjan(goal);
low[x]=min(low[x],low[goal]);
}
else if(/*vis[goal]*/!id[goal])
low[x]=min(low[x],dfn[goal]);
}
if(low[x]==dfn[x]){
re++;int v;
do{
v=sta[ans--];
vis[v]=0;
id[v]=re;
}while(v!=x);
}
return 1;
}
int topsort(int n){
ans=0;
for(int i=1;i<=re;i++){
if(in[i]==0){
sta[ans++]=i;
}
}
if(ans>1)return 0;
while(ans>0){
ans--;
int qtop=sta[ans];
for(int j=head2[qtop];j!=-1;j=next2[j]){
in[vec2[j]]--;
if(in[vec2[j]]==0)
sta[ans++]=vec2[j];
}
if(ans>1)
return 0;
}
return 1;
}
int main()
{
int tcase,n,m,s,e;
scanf("%d",&tcase);
while(tcase--){
//system("PAUSE");
init();
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",&s,&e);
addedge(s,e);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
{
tarjan(i);
}
if(re==1){
printf("Yes
");
continue;
}
for(int i=1;i<=n;i++){
for(int j=head[i];j!=-1;j=next[j]){
if(id[vec[j]]!=id[i]){
in[id[vec[j]]]++;
addedge2(id[i],id[vec[j]]);
}
}
}
if(topsort(re))printf("Yes
");
else printf("No
");
}
return 0;
}