留个e-DCC的板子
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; struct node { int x,y,next; }a[4100000];int len,last[1100000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } int z,dfn[1100000],low[1100000]; bool b[1100000]; void tarjan(int x,int fr) { dfn[x]=low[x]=++z; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(dfn[y]==0) { tarjan(y,x); low[x]=min(low[x],low[y]); if(dfn[x]<low[y]) b[k]=b[k^1]=true; } if(y!=fr) low[x]=min(low[x],dfn[y]); } } int cnt,bel[1100000]; void sdfj(int x,int fr) { bel[x]=cnt; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(bel[y]==0&&b[k]==false) sdfj(y,x); } } //--------------------缩点---------------------- int Bin[25]; int f[25][1100000],dep[1100000]; void dfs(int x) { for(int i=1;dep[x]>=Bin[i];i++)f[i][x]=f[i-1][f[i-1][x]]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=f[0][x]) { f[0][y]=x; dep[y]=dep[x]+1; dfs(y); } } } int LCA(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=22;i>=0;i--) if(dep[x]-dep[y]>=Bin[i])x=f[i][x]; if(x==y)return x; for(int i=22;i>=0;i--) if(dep[x]>=Bin[i]&&f[i][x]!=f[i][y])x=f[i][x],y=f[i][y]; return f[0][x]; } int main() { int n,m,T_T=0; scanf("%d%d",&n,&m); len=1;memset(last,0,sizeof(last)); int x,y; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); ins(x,y);ins(y,x); } z=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(b,false,sizeof(b)); tarjan(1,0); cnt=0; memset(bel,0,sizeof(bel)); for(int i=1;i<=n;i++) if(bel[i]==0) cnt++, sdfj(i,0); int tp=0; memset(last,0,sizeof(last)); for(int i=1;i<=len;i++) { if(bel[a[i].x]!=bel[a[i].y]) { tp++; a[tp].x=bel[a[i].x]; a[tp].y=bel[a[i].y]; a[tp].next=last[a[tp].x]; last[a[tp].x]=tp; } } len=tp; Bin[0]=1;for(int i=1;i<=22;i++)Bin[i]=Bin[i-1]*2; f[0][1]=0;dep[1]=0;dfs(1); int Q,ans=cnt-1; scanf("%d",&Q); while(Q--) { scanf("%d%d",&x,&y);x=bel[x],y=bel[y]; int lca=LCA(x,y); printf("%d ",dep[x]-dep[lca]+dep[y]-dep[lca]); } return 0; }