首页 > 代码库 > POJ 2762 Going from u to v or from v to u? (图论-tarjan)
POJ 2762 Going from u to v or from v to u? (图论-tarjan)
Going from u to v or from v to u?
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 14469 | Accepted: 3801 |
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
题目大意:
解题思路:T组测试数据,n个点,m有向条边,然后问你这个图是否满足任意两个点u到v或者v到u
解题代码:参照我的博客这篇文章,就知道解法了:http://blog.csdn.net/a1061747415/article/details/38380665
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <algorithm> using namespace std; const int maxn=1100; const int maxm=51000; struct edge{ int u,v,next; edge(int u0=0,int v0=0){ u=u0;v=v0; } }e[maxm]; int n,m,head[maxn],dfn[maxn],low[maxn],mark[maxn],w[maxn],color[maxn],dp[maxn],cnt,nc,index; vector <int> vec; vector <vector<int> > dfsmap; void addedge(int u,int v){ e[cnt]=edge(u,v);e[cnt].next=head[u];head[u]=cnt++; } void input(){ cnt=nc=index=0; scanf("%d%d",&n,&m); vec.clear(); for(int i=0;i<=n;i++){ w[i]=dfn[i]=0; mark[i]=false; color[i]=dp[i]=head[i]=-1; } int u,v; while(m-- >0){ scanf("%d%d",&u,&v); addedge(u,v); } } void tarjan(int s){ dfn[s]=low[s]=++index; mark[s]=true; vec.push_back(s); for(int i=head[s];i!=-1;i=e[i].next){ int d=e[i].v; if(!dfn[d]){ tarjan(d); low[s]=min(low[d],low[s]); }else if(mark[d]){ low[s]=min(low[s],dfn[d]); } } if(dfn[s]==low[s]){ nc++; int d; do{ d=vec.back(); vec.pop_back(); color[d]=nc; mark[d]=false; w[nc]++; }while(d!=s); } } int DP(int s){ if(dp[s]!=-1) return dp[s]; int ans=w[s]; for(int i=0;i<dfsmap[s].size();i++){ int d=dfsmap[s][i]; if(DP(d)+w[s]>ans) ans=DP(d)+w[s]; } return dp[s]=ans; } void solve(){ for(int i=1;i<=n;i++){ if(!dfn[i]) tarjan(i); } dfsmap.clear(); dfsmap.resize(nc+1); for(int i=0;i<cnt;i++){ int x=color[e[i].u],y=color[e[i].v]; if(x!=y){ dfsmap[x].push_back(y); //cout<<x<<"->"<<y<<endl; } } int ans=0; for(int i=1;i<=nc;i++){ if(DP(i)>ans) ans=DP(i); //cout<<i<<" "<<ans<<endl; } if(ans>=n) printf("Yes\n"); else printf("No\n"); } int main(){ int t; scanf("%d",&t); while(t-- >0){ input(); solve(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。