江老板说tarjan模板题,然后就抄了板子,其实并不懂为什么。。。。
#include<bits/stdc++.h> using namespace std; const int N=26000; const int M=50050; int e[M][2],cut[M],g[N],v[M<<1],nxt[M<<1],ed; int f[N],dfn[N],low[N],num,cnt,from[N]; void add(int x,int y) { v[++ed]=y; nxt[ed]=g[x]; g[x]=ed; } void tarjan(int x) { dfn[x]=low[x]=++num; for(int i=g[x];i;i=nxt[i]) { if(!dfn[v[i]]) { f[v[i]]=i>>1; tarjan(v[i]); if(low[x]>low[v[i]]) low[x]=low[v[i]]; } else if(f[x]!=(i>>1)&&low[x]>dfn[v[i]]) low[x]=dfn[v[i]]; } if(f[x]&&low[x]==dfn[x]) cut[f[x]]=1; } void dfs(int x,int y) { from[x]=y; for(int i=g[x];i;i=nxt[i]) { if(!from[v[i]]&&!cut[i>>1]) dfs(v[i],y); } } int main() { int n,m,i,x,y,q; while(scanf("%d%d",&n,&m)!=EOF) { memset(cut,0,sizeof(cut)); memset(g,0,sizeof(g)); memset(v,0,sizeof(v)); memset(nxt,0,sizeof(nxt)); memset(f,0,sizeof(f)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(from,0,sizeof(from)); num=cnt=0; for(ed=i=1;i<=m;i++) { scanf("%d%d",&x,&y); e[i][0]=x; e[i][1]=y; add(x,y); add(y,x); } for(i=1;i<=n;i++) { if(!dfn[i]) tarjan(i); } for(i=1;i<=n;i++) { if(!from[i]) dfs(i,++cnt); } scanf("%d",&q); while(q--) { scanf("%d%d",&x,&y); if(from[x]==from[y]) printf("Yes\n"); else printf("No\n"); } } }