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

本文主要是介绍Going from u to v or from v to u? POJ - 2762，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=2762

问是否任意两点uv都满足u可达v或v可达u 先强连通缩点 然后暴力n^2扫一遍

应该有更好的办法 留坑

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int maxn=1e3+10;
const int maxm=6e3+10;struct node
{int v,next;
};stack <int> stk;
node edge1[maxm],edge2[maxm];
bool e[maxn][maxn];
int first1[maxn],first2[maxn],dfn[maxn],low[maxn],book[maxn],belong[maxn];
int n,m,num,cnt;void addedge(node *edge,int *first,int u,int v)
{edge[num].v=v;edge[num].next=first[u];first[u]=num++;
}void init()
{int i;for(i=1;i<=n;i++){dfn[i]=0,low[i]=0,book[i]=0;}
}void dfsI(int cur)
{int i,v;stk.push(cur);num++;dfn[cur]=num,low[cur]=num,book[cur]=1;for(i=first1[cur];i!=-1;i=edge1[i].next){v=edge1[i].v;if(!dfn[v]){dfsI(v);low[cur]=min(low[cur],low[v]);}else if(book[v]){low[cur]=min(low[cur],dfn[v]);}}if(dfn[cur]==low[cur]){cnt++;while(!stk.empty()){v=stk.top();stk.pop();book[v]=0;belong[v]=cnt;if(v==cur) break;}}
}void tarjan()
{int i;init();num=0,cnt=0;for(i=1;i<=n;i++){if(!dfn[i]){dfsI(i);}}
}void rebuild()
{int i,u,v;for(i=1;i<=n;i++) first2[i]=-1;num=0;for(u=1;u<=n;u++){for(i=first1[u];i!=-1;i=edge1[i].next){v=edge1[i].v;if(belong[u]!=belong[v]){addedge(edge2,first2,belong[u],belong[v]);}}}
}void dfsII(int u,int cur)
{int i,v;e[u][cur]=1;for(i=first2[cur];i!=-1;i=edge2[i].next){v=edge2[i].v;if(!book[v]){book[v]=1;dfsII(u,v);}}
}bool solve()
{int i,j;for(i=1;i<=cnt;i++){for(j=1;j<=cnt;j++){e[i][j]=0;}}for(i=1;i<=cnt;i++){for(j=1;j<=cnt;j++) book[j]=0;book[i]=1;dfsII(i,i);}for(i=1;i<=cnt;i++){for(j=1;j<=cnt;j++){if(!e[i][j]&&!e[j][i]) return 0;}}return 1;
}int main()
{int t,i,u,v;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(i=1;i<=n;i++) first1[i]=-1;num=0;while(m--){scanf("%d%d",&u,&v);addedge(edge1,first1,u,v);}tarjan();rebuild();if(solve()) printf("Yes\n");else printf("No\n");}return 0;
}

 

这篇关于Going from u to v or from v to u? POJ - 2762的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---