Description

【题意】0x60图论（练习）15：逃不掉的路
给出一个有 $n$ 个点 $m$ 条边的无向图，保证连通。
有 $q$ 次询问，每次询问给出两个整数 $a \ b$，统计 $a, b$ 两点之间割边的数量（即 $a$点 到 $b$点 的所有路径中，必须经过的边的数量）。

【输入格式】
第一行两个整数是 $n$，$m$ （$n \le 10^5$,$m \le 2 \times 10^5$）。
下来 $m$ 行，每行两个整数 $x$，$y$（$1 \le x,y \le n$） ，表示 $x$ 和 $y$ 之间的一条无向边。同一条边不会出现两次。
下来一个整数 $q$（$q≤10^5$）。
下来 $q$ 行，每行两个整数$a$，$b$（$a \ne b , 1 \le a,b \le n$），表示一次询问。

【输出格式】
对于每次询问，输出一行一个整数，表示 $a, b$ 两点之间割边的数量。

【输入样例】
5 5
1 2
1 3
2 4
3 4
4 5
2
1 4
2 5

【输出样例】
0
1

Hint

标程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&#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;
}

fa[0]=dep[0]=siz[0]=0;memset(son&#44;0&#44;sizeof(son));
dfs1(1&#44;0);
dfs2(1&#44;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;

}

暴力LCA的代码48ms：</p>

#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,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(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;
}

Source

S8.0