首页 > 代码库 > poj 2762 Going from u to v or from v to u?
poj 2762 Going from u to v or from v to u?
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 17689 | Accepted: 4745 |
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
题目大意
给出一些点,和他们之间的有向边,如果图中任意两点 x,y 之间满足 x 可以到达 y 或者 y 可以到达 x ,就输出“Yes”,否则输出“No”
因为n>1000 所以挨个判断是不可取的
所以我们用tarjan 求出强连通分量的个数
然后判断这几个强连通分量在不在一条链上就可以了
tarjan缩点+拓扑排序
屠龙宝刀点击就送
#include <cstring>#include <ctype.h>#include <cstdio>#include <queue>#define M 6005#define N 1500using namespace std;void read(int &x){ x=0;bool f=0; char ch=getchar(); while(!isdigit(ch)) { if(ch==‘-‘) f=1; ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-‘0‘; ch=getchar(); } x=f?(~x)+1:x;}int in[N],g[N][N],tim,dfn[N],col[N],sumcol,low[N],T,n,m,head[N],cnt,stack[N],top;bool instack[N],vis[N];struct node{ int next,to;}edge[M];void add(int u,int v){ edge[++cnt].next=head[u]; edge[cnt].to=v; head[u]=cnt;}int min(int a,int b){ return a>b?b:a;}void dfs(int x){ stack[++top]=x; instack[x]=1; vis[x]=1; low[x]=dfn[x]=++tim; for(int i=head[x];i;i=edge[i].next) { int v=edge[i].to; if(instack[v]) low[x]=min(low[x],dfn[v]); else if(!vis[v]) { dfs(v); low[x]=min(low[x],low[v]); } } if(low[x]==dfn[x]) { sumcol++; while(x!=stack[top]) { instack[stack[top]]=0; col[stack[top--]]=sumcol; } instack[stack[top]]=0; col[stack[top--]]=sumcol; }}bool judge(){ queue<int>q; for(int i=1;i<=sumcol;i++) if(!in[i]) q.push(i); if(q.size()>1) return false; while(!q.empty()) { int now=q.front(); q.pop(); for(int i=1;i<=sumcol;i++) if(g[now][i]) { in[i]--; if(!in[i]) q.push(i); } if(q.size()>1) return false; } return true;}int main(){ read(T); for(;T--;) { memset(head,0,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(vis,0,sizeof(vis)); memset(instack,0,sizeof(instack)); memset(col,0,sizeof(col)); memset(low,0,sizeof(low)); memset(in,0,sizeof(in)); memset(g,0,sizeof(g)); tim=0;top=0;sumcol=0;cnt=0; bool f=false; read(n); read(m); for(int x,y,i=1;i<=m;i++) { read(x); read(y); add(x,y); } for(int i=1;i<=n;i++) if(!vis[i]) dfs(i); if(sumcol==1) {printf("Yes\n");continue;} for(int i=1;i<=n;i++) { for(int j=head[i];j;j=edge[j].next) { int v=edge[j].to; if(i!=v&&col[i]!=col[v]) { g[col[i]][col[v]]=1; in[col[v]]++; } } } if(judge()) printf("Yes\n"); else printf("No\n"); } return 0;}
poj 2762 Going from u to v or from v to u?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。