https://www.cnblogs.com/Tyouchie/p/10426016.html

题目描述

现代社会，路是必不可少的。

共有n个城镇，m条道路，任意两个城镇都有路相连，而且往往不止一条。

但有些路年久失修，走着很不爽。

按理说条条大路通罗马，大不了绕行其他路呗——可小撸却发现：从a城到b城不管怎么走，总有一些逃不掉的必经之路。

他想请你计算一下，a到b的所有路径中，有几条路是逃不掉的？

输入格式
第一行是n和m，用空格隔开。

接下来m行，每行两个整数x和y，用空格隔开，表示x城和y城之间有一条长为1的双向路。

第m+2行是q。

接下来q行，每行两个整数a和b，用空格隔开，表示一次询问。

输出格式
对于每次询问，输出一个正整数，表示a城到b城必须经过几条路。

每个输出占一行。

数据范围
n≤105,m≤2∗105,q≤105
对于全部的数据，1≤x,y,a,b≤n；对于任意的道路，两端的城市编号之差不超过104；
任意两个城镇都有路径相连；同一条道路不会出现两次；道路的起终点不会相同;查询的两个城市不会相同。

输入样例：
5 5
1 2
1 3
2 4
3 4
4 5
2
1 4
2 5
输出样例：
0
1
思路：
既然是求必须经过的边，那么边双包含的集合肯定不是必须经过的，就可以把所有边双缩点；

原图得到一颗树后，问题就变成了简单的求树上两点之间的距离。

这个题就是lca+边双的题啦：

注意：

边双连通分量缩点后，原图变成一颗真正的树，而树上各种操作可以和其他知识点结合起来。

这种敏感性要有，比如缩点之后就可以快速求必经边，必经点之类的。

鬼知道我因为a和e打错调了多长时间；

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
template<typename T>inline void read(T &x) {
    x=0;
    T f=1,ch=getchar();
    while (!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}
struct gg {
    int y,next,v;
}a[N<<1],e[N<<1];
int tot=1,tc=1;
int n,m,q,x,y,num,dcc;
int d[N],f[N][25],dfn[N],low[N],lin[N],linc[N],bridge[N<<1],c[N];
inline void add(int x,int y) {
    a[++tot].y=y; a[tot].next=lin[x]; lin[x]=tot;
}
inline void tarjan(int x,int in_edge) {
    dfn[x]=low[x]=++num;
    for(int i=lin[x];i;i=a[i].next) {
        int y=a[i].y;
        if(!dfn[y]) {
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x]) {
                bridge[i]=bridge[i^1]=1;
            }
        }
        else if(i!=(in_edge^1))
            low[x]=min(low[x],dfn[y]);
    } 
}
inline void dfs(int x) {//求出每个边双； 
    c[x]=dcc;
    for(int i=lin[x];i;i=a[i].next) {
        int y=a[i].y;
        if(c[y]||bridge[i]) continue;
        dfs(y);
    }
}
inline void add_c(int x,int y) {
    e[++tc].y=y; e[tc].next=linc[x]; linc[x]=tc;
}
inline void bfs() {
    queue<int> q;
    q.push(1);d[1]=1;
    while(q.size()) {
        int x=q.front();q.pop();
        for(int i=linc[x];i;i=e[i].next) {
            int y=e[i].y;
            if(d[y]) continue;
            d[y]=d[x]+1;
            f[y][0]=x;
            for(int j=1;j<=23;j++)
                f[y][j]=f[f[y][j-1]][j-1];
            q.push(y);
        }
    }
}
inline int lca(int x,int y) {
    if(d[x]>d[y]) swap(x,y);
    for(int i=23;i>=0;i--)
        if(d[f[y][i]]>=d[x]) y=f[y][i];
    if(x==y) return x;
    for(int i=23;i>=0;i--)
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main() {
    read(n); read(m);
    for(int i=1;i<=m;i++) {
        read(x); read(y);
        add(x,y); add(y,x);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i,-1);
    for(int i=1;i<=n;i++) {
        if(!c[i]) {
            ++dcc;
            dfs(i);
        }
    }
    for(int i=2;i<=tot;i++) {
        int x=a[i^1].y,y=a[i].y;
        if(c[x]==c[y]) continue;
        add_c(c[x],c[y]);
        add_c(c[y],c[x]);
    } 
    bfs();
    read(q);
    while(q--) {
        read(x); read(y);
        x=c[x]; y=c[y];
        printf("%d\n",d[x]+d[y]-2*d[lca(x,y)]);
    }
    return 0;
}