POJ 2762 Going from u to v or from v to u?

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

卡在读题。。。

题意：

给定一副有向图，选择两个点v和u，要求v能到达u或者u能到达v。

问是否可以对于图中的每一个点对<v, u>都能满足条件？输出Yes或No。

首先，想到tarjan缩点，之后原图变成DAG，通过观察发现只有当他是一条链时，才成立，dfs一遍就好了。

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<stack> using namespace std; const int N=10005; const int M=60005; int T,n,m,cnt,tim,dcnt,hd[N],low[N],dfn[N],belong[N],x[M],y[M],du[N]; bool flg,ins[N]; stack<int>stk; struct edge { int to,nxt; }v[M]; void addedge(int x,int y) { v[++cnt].to=y; v[cnt].nxt=hd[x]; hd[x]=cnt; } void tarjan(int u) { dfn[u]=low[u]=++tim; stk.push(u); ins[u]=1; for(int i=hd[u];i;i=v[i].nxt) if(!dfn[v[i].to]) { tarjan(v[i].to); low[u]=min(low[u],low[v[i].to]); } else if(ins[v[i].to]) low[u]=min(low[u],dfn[v[i].to]); if(dfn[u]==low[u]) { ++dcnt; while(1) { int t=stk.top(); stk.pop(); ins[t]=0; belong[t]=dcnt; if(u==t) break; } } } void dfs(int u) { int sum=0; for(int i=hd[u];i;i=v[i].nxt) { sum++; dfs(v[i].to); } if(sum>1) flg=1; } int main() { scanf("%d",&T); while(T--) { flg=0; cnt=dcnt=tim=0; memset(hd,0,sizeof(hd)); memset(du,0,sizeof(du)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&x[i],&y[i]); addedge(x[i],y[i]); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); cnt=0; memset(hd,0,sizeof(hd)); for(int i=1;i<=m;i++) if(belong[x[i]]!=belong[y[i]]) { addedge(belong[x[i]],belong[y[i]]); du[belong[y[i]]]++; } int sum=0; for(int i=1;i<=dcnt;i++) if(du[i]==0) { sum++; dfs(i); } if(sum>1||flg) printf("No\n"); else printf("Yes\n"); } return 0; }