poj2762 Going from u to v or from v to u?
#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>#define N 1051#define E 30000#define M 1000000using namespace std;int head[N],head2[N],next2[E],vec2[E],sta[M],re,ans,next[E],id[N],in[N],vec[E],vis[N],dfn[N],low[N],clock_m,edge_m,edge_m2;int addedge(int s,int e){ vec[edge_m]=e;next[edge_m]=head[s];head[s]=edge_m++;}int addedge2(int s,int e){ vec2[edge_m2]=e;next2[edge_m2]=head2[s];head2[s]=edge_m2++;}int init(){ memset(vis,0,sizeof(vis)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(head,-1,sizeof(head)); memset(head2,-1,sizeof(head2)); memset(id,0,sizeof(id)); memset(in,0,sizeof(in)); edge_m=0;clock_m=0;ans=0;re=0;edge_m2=0;}int tarjan(int x){ dfn[x]=low[x]=++clock_m; sta[++ans]=x; vis[x]=1; for(int i=head[x];i!=-1;i=next[i]){ int goal=vec[i]; if(!dfn[goal]){ tarjan(goal); low[x]=min(low[x],low[goal]); } else if(/*vis[goal]*/!id[goal]) low[x]=min(low[x],dfn[goal]); } if(low[x]==dfn[x]){ re++;int v; do{ v=sta[ans--]; vis[v]=0; id[v]=re; }while(v!=x); } return 1;}int topsort(int n){ ans=0; for(int i=1;i<=re;i++){ if(in[i]==0){ sta[ans++]=i; } } if(ans>1)return 0; while(ans>0){ ans--; int qtop=sta[ans]; for(int j=head2[qtop];j!=-1;j=next2[j]){ in[vec2[j]]--; if(in[vec2[j]]==0) sta[ans++]=vec2[j]; } if(ans>1) return 0; } return 1;}int main(){ int tcase,n,m,s,e; scanf("%d",&tcase); while(tcase--){ //system("PAUSE"); init(); scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d",&s,&e); addedge(s,e); } for(int i=1;i<=n;i++) if(!dfn[i]) { tarjan(i); } if(re==1){ printf("Yes\n"); continue; } for(int i=1;i<=n;i++){ for(int j=head[i];j!=-1;j=next[j]){ if(id[vec[j]]!=id[i]){ in[id[vec[j]]]++; addedge2(id[i],id[vec[j]]); } } } if(topsort(re))printf("Yes\n"); else printf("No\n"); } return 0;}
