标程（88ms）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<pair<int,int>>G1[N];
vector<int>G2[N];
 
int tsp,cnt,dfn[N],low[N],scc[N];stack<int>stk;bool instk[N];

void tarjan(int x, int in_id) 
{
    dfn[x] = low[x] = ++tsp;
    stk.push(x);instk[x]=1;
    for(auto i:G1[x]) if(i.second!= in_id)
	{
        int y=i.first,id=i.second;
        if (dfn[y]==0) 
		{
            tarjan(y,id);
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y])low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
    {
	    cnt++;
	    for(int z=-1;z!=x;)
	    {
	    	z=stk.top();stk.pop();instk[z]=0;
	    	scc[z]=cnt;}
	}
}

int fa[N],son[N],dep[N],siz[N];
void dfs1(int x,int xfa) 
{
	fa[x]=xfa;dep[x]=dep[xfa]+1;siz[x]=1;
	for(int y:G2[x])if(y!=xfa)
	{
		dfs1(y,x);
		siz[x]+=siz[y];
		if(siz[son[x]]<siz[y])son[x]=y;
    }
}
int top[N];
void dfs2(int x, int tp) 
{ 
    top[x]=tp;
    if(son[x]!=0) dfs2(son[x],tp); 
    for(int y:G2[x])if(y!=fa[x] && y!=son[x])
    	dfs2(y,y);
}
int lca(int x, int y)
{
    while(top[x]!=top[y]) 
    { 
        if( dep[ top[x] ] < dep[ top[y] ] ) swap(x,y);
        x=fa[top[x]];
    } 
    if(dep[x]>dep[y])swap(x,y);  
    return x;
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);    
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        G1[x].push_back({y,i});
        G1[y].push_back({x,i});
    }
         
    tsp=cnt=0;memset(low,0,sizeof low);memset(dfn,0,sizeof dfn);
	memset(scc,0,sizeof(scc));memset(instk,0,sizeof(instk));
    tarjan(1,0);

    map<pair<int,int>,bool>mp;
    for (int i=1;i<=n;i++)for(auto t:G1[i]) 
    {
        int x=scc[i], y=scc[t.first];if(x>y)swap(x,y);
        if(x!=y && !mp[{x,y}]) G2[x].push_back(y),G2[y].push_back(x),mp[{x,y}]=1;
    }
    
    fa[0]=dep[0]=siz[0]=0;memset(son,0,sizeof(son));
    dfs1(1,0);
    dfs2(1,1);
    
    int q;scanf("%d",&q);
    for(int i=1,x,y;i<=q;i++)
    {
        scanf("%d%d", &x, &y);
        x=scc[x],y=scc[y];printf("%d\n", dep[x]+dep[y]-2*dep[lca(x,y)]);}}

暴力LCA（48ms）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e+10;
vector<pair<int,int>>G1[N];
vector<int>G2[N];
  
int tsp,cnt,dfn[N],low[N],scc[N];stack<int>stk;bool instk[N];
 
void tarjan(int x, int in_id) 
{
    dfn[x] = low[x] = ++tsp;
    stk.push(x);instk[x]=1;
    for(auto i:G1[x]) if(i.second!= in_id) {
        int y=i.first,id=i.second;
        if (dfn[y]==0) {tarjan(y,id);low[x]=min(low[x],low[y]);}
        else if(instk[y])low[x]=min(low[x],dfn[y]);}
    if(dfn[x]==low[x]){
        cnt++;for(int z=-1;z!=x;){
            z=stk.top();stk.pop();instk[z]=0;scc[z]=cnt;}}}
 
int dep[N]/*缩点后深度*/, fa[N]/*缩点后父节点*/;
void dfs_scc(int x) {for(int y:G2[x])if(dep[y]==0){
    dep[y]=dep[x]+1;fa[y]=x;dfs_scc(y);}}
  
int lca(int x, int y) {while(x!=y){if(dep[x]<dep[y])swap(x,y);x=fa[x];}return x;}
  
int main() {
    int n,m;scanf("%d%d",&n,&m);for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);G1[x].push_back({y,i});G1[y].push_back({x,i});}
          
    tsp=cnt=0;memset(low,0,sizeof low);memset(dfn,0,sizeof dfn);
    memset(scc,0,sizeof(scc));memset(instk,0,sizeof(instk));tarjan(1,0);

    map<pair<int,int>,bool>mp;for(int i=1;i<=n;i++)for(auto t:G1[i]){
        int x=scc[i],y=scc[t.first];if(x>y)swap(x,y);
        if(x!=y && !mp[{x,y}])G2[x].push_back(y),G2[y].push_back(x),mp[{x,y}]=1;}
          
    memset(fa,0,sizeof(fa));memset(dep,0,sizeof(dep));dep[1]=1;dfs_scc(

标程88ms：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<pair<int,int>>G1[N];
vector<int>G2[N];
 
int tsp,cnt,dfn[N],low[N],scc[N];
stack<int>stk;bool instk[N];

void tarjan(int x, int in_id) 
{
    dfn[x] = low[x] = ++tsp;
    stk.push(x);instk[x]=1;
    for(auto i:G1[x]) if(i.second!= in_id)
	{
        int y=i.first,id=i.second;
        if (dfn[y]==0) 
		{
            tarjan(y,id);
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y])low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
    {
	    cnt++;
	    for(int z=-1;z!=x;)
	    {
	    	z=stk.top();stk.pop();instk[z]=0;
	    	scc[z]=cnt;
	    }
	}
}

int fa[N],son[N],dep[N],siz[N];
void dfs1(int x,int xfa) 
{
	fa[x]=xfa;dep[x]=dep[xfa]+1;siz[x]=1;
	for(int y:G2[x])if(y!=xfa)
	{
		dfs1(y,x);
		siz[x]+=siz[y];
		if(siz[son[x]]<siz[y])son[x]=y;
    }
}
int top[N];
void dfs2(int x,int tp) 
{ 
    top[x]=tp;
    if(son[x]!=0) dfs2(son[x],tp); 
    for(int y:G2[x])if(y!=fa[x] && y!=son[x])
    	dfs2(y,y);
}
int lca(int x,int y)
{
    while(top[x]!=top[y]) 
    { 
        if( dep[ top[x] ] < dep[ top[y] ] ) swap(x,y);
        x=fa[top[x]];//x跳到自己所在重链起始端的父亲 
    } 
    if(dep[x]>dep[y])swap(x,y);  
    return x;
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);    
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        G1[x].push_back({y,i});
        G1[y].push_back({x,i});
    }
         
    tsp=cnt=0;memset(low,0,sizeof low);memset(dfn,0,sizeof dfn);
	memset(scc,0,sizeof(scc));memset(instk,0,sizeof(instk));
    tarjan(1,0);

    map<pair<int,int>,bool>mp;
    for (int i=1;i<=n;i++)for(auto t:G1[i]) 
    {
        int x=scc[i], y=scc[t.first];if(x>y)swap(x,y);
        if(x!=y && !mp[{x,y}]) G2[x].push_back(y),G2[y].push_back(x),mp[{x,y}]=1;
    }
    
    fa[0]=dep[0]=siz[0]=0;memset(son,0,sizeof(son));
    dfs1(1,0);
    dfs2(1,1);
    
    int q;scanf("%d",&q);
    for(int i=1,x,y;i<=q;i++)
    {
        scanf("%d%d", &x, &y);
        x=scc[x],y=scc[y];
        printf("%d\n", dep[x]+dep[y]-2*dep[lca(x,y)]);
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<pair<int,int>>G1[N];
vector<int>G2[N];
int tsp,cnt,dfn[N],low[N],scc[N];
stack<int>stk;bool instk[N];
void tarjan(int x, int in_id)
{
dfn[x] = low[x] = ++tsp;
stk.push(x);instk[x]=1;
for(auto i:G1[x]) if(i.second!= in_id)
{
int y=i.first,id=i.second;
if (dfn[y]==0)
{
tarjan(y,id);
low[x]=min(low[x],low[y]);
}
else if(instk[y])low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
cnt++;
for(int z=-1;z!=x;)
{
z=stk.top();stk.pop();instk[z]=0;
scc[z]=cnt;
}
}
}
int dep[N]/缩点之后的树上的深度/, fa[N]/缩点之后的树上的父节点/;
void dfs_scc(int x)
{
for (int y:G2[x])if(dep[y]==0)
{
dep[y]=dep[x]+1;
fa[y]=x;
dfs_scc(y);
}
}
int lca(int x,int y)
{

while(x!=y)
{
if(dep[x]<dep[y])swap(x,y);
x=fa[x];
}
return x;
}
int main()
{
int n,m;scanf("%d%d",&n,&m);

for(int i=1,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
G1[x].push_back({y,i});
G1[y].push_back({x,i});
}
tsp=cnt=0;memset(low&#44;0&#44;sizeof low);memset(dfn&#44;0&#44;sizeof dfn);
memset(scc&#44;0&#44;sizeof(scc));memset(instk&#44;0&#44;sizeof(instk));
tarjan(1&#44;0);

map&lt;pair&lt;int&#44;int&gt;&#44;bool&gt;mp;
for (int i=1;i&lt;=n;i++)for(auto t:G1[i]) 
{
    int x=scc[i]&#44; y=scc[t.first]; if(x&gt;y)swap(x&#44;y);
    if(x!=y &amp;&amp; !mp[{x&#44;y}])  G2[x].push_back(y)&#44;G2[y].push_back(x)&#44;mp[{x&#44;y}]=1;
}
      
memset(fa&#44;0&#44;sizeof(fa));memset(dep&#44;0&#44;sizeof(dep));
dep[1]=1&#44;dfs_scc(1);
 
int q;scanf("%d"&#44;&amp;q);
for(int i=1&#44;x&#44;y;i&lt;=q;i++)
{
    scanf("%d%d"&#44; &amp;x&#44; &amp;y);
    x=scc[x]&#44;y=scc[y];
    printf("%d\n"&#44; dep[x]+dep[y]-2*dep[lca(x&#44;y)]);
}
return 0;

}