首页 > 代码库 > poj Going from u to v or from v to u?
poj Going from u to v or from v to u?
Going from u to v or from v to u?
| Time Limit: 2000MS | Memory Limit: 65536K |
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
13 31 22 33 1
Sample Output
Yes
Source
POJ Monthly--2006.02.26,zgl & twb
思路：Tarjan+拓扑排序。
喜闻乐见的Code
#include<cstdio>#include<algorithm>using namespace std;#define maxn 1010#define maxm 6010struct Edge { int u,v,next; Edge(int u=0,int v=0,int next=0): u(u),v(v),next(next) {}}edge[maxm],EDGE[maxm];int head[maxn],HEAD[maxn],rd[maxn];int dfn[maxn],low[maxn],st[maxn],col[maxn];int cnt,CNT,timee,top,numcolor;bool ins[maxn],vis[maxn];inline int input() { char c=getchar();int x=0,flag=1; for(;c<‘0‘||c>‘9‘;c=getchar()) if(c==‘-‘) flag=-1; for(;c>=‘0‘&&c<=‘9‘;c=getchar()) x=(x<<1)+(x<<3)+c-‘0‘; return x*flag;}inline void Add_edge(int u,int v,bool flag) { if(flag) edge[++cnt]=Edge(u,v,head[u]),head[u]=cnt; else EDGE[++CNT]=Edge(u,v,HEAD[u]),HEAD[u]=CNT; return;}void dfs(int now) { dfn[now]=low[now]=++timee; st[++top]=now; ins[now]=vis[now]=true; for(int i=head[now];i;i=edge[i].next) { int v=edge[i].v; if(ins[v]) low[now]=min(low[now],dfn[v]); else if(!vis[v]) { dfs(v); low[now]=min(low[now],low[v]); } } if(dfn[now]==low[now]) { col[now]=++numcolor; while(st[top]!=now) { col[st[top]]=numcolor; ins[st[top--]]=false; } ins[now]=false; top--; } return;}inline bool topo() { int pos,count=0; for(int i=1;i<=numcolor;i++) if(rd[i]==0) pos=i,count++; if(count>1) return false; for(int k=1;k<=numcolor;k++) { count=0; for(int i=HEAD[pos];i;i=EDGE[i].next) { int v=EDGE[i].v; rd[v]--; if(rd[v]==0) pos=i,count++; } if(count>1) return false; } return true;}int main() { for(int t=input();t;t--) { int n=input(),m=input(); for(int i=1;i<=n;i++) { ins[i]=vis[i]=false; head[i]=HEAD[i]=rd[i]=0; col[i]=dfn[i]=low[i]=st[i]=0; } cnt=CNT=top=timee=numcolor=0; for(int i=1;i<=m;i++) { int u=input(),v=input(); Add_edge(u,v,1); } for(int i=1;i<=n;i++) if(!vis[i]) dfs(i); for(int i=1;i<=m;i++) { int u=edge[i].u,v=edge[i].v; if(col[u]!=col[v]) { Add_edge(col[u],col[v],0); rd[col[v]]++; } } topo()?printf("Yes\n"):printf("No\n"); } return 0;}
poj Going from u to v or from v to u?
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。