【题解】Luogu P2783 有机化学之神偶尔会做作弊

原题链接：P2783 有机化学之神偶尔会做作弊

一看，是黑题，太毒瘤了，不写

什么单链？？！

只会画有机化学中正六边形的我觉得这样不行QAQ（我才初二）

当然，题目也给你了详细的解释

实际呢，这道题先给你了一个图，让你把图中的环全缩成一个点，在求两个点之间的距离

这道题估计是你谷最简单黑题

先用tarjan缩点，再重新建图

在新建的图上跑lca求距离

就是这么简单

代码上有些细节需要注意

#pragma GCC optimize("O3")

#define N 100001

#include <bits/stdc++.h>

using namespace std;

inline int read()

{

    register int f=1,x=0;

    register char ch;

    do{

        ch=getchar();

        if(ch=='-')

            f=-1;

    }while(ch<'0'||ch>'9');

    do{

        x=x*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return f*x;

}

inline int Min(register int a,register int b)

{

    if(a<b)

        return a;

    return b;

}

inline void Swap(register int &a,register int &b)

{

    a^=b^=a^=b;

}

int tmp[64];

inline void print(register int res)

{

    if(res==0)

    {

        puts("0");

        return;

    }

    if(res<0)

    {

        putchar('-');

        res=0-res;

    }

    while(res)

        tmp[++tmp[0]]=res&1,res>>=1;

    while(*tmp)

        putchar(tmp[(*tmp)--]+'0');

    putchar('\n');

}

int n,m,tot,q,sign,top,cnt;

int first[N<<1][2],next[N<<1][2],to[N<<1][2],dfn[N],low[N],sta[N],id[N],dep[N];

int p[N][50],xx[N],yy[N];

bool insta[N];

inline void ADD(register int x,register int y,register int w)

{

    next[++tot][w]=first[x][w];

    to[tot][w]=y;

    first[x][w]=tot;

}

inline void add(register int x,register int y,register int w)

{

    ADD(x,y,w);

    ADD(y,x,w);

}

inline void DFS(register int x,register int fa)

{

    dfn[x]=low[x]=++sign;

    sta[++top]=x;

    insta[x]=true;

    int k=first[x][0],u;

    while(k)

    {

        u=to[k][0];

        if(u==fa)

        {

            k=next[k][0];

            continue;

        }

        if(!dfn[u])

        {

            DFS(u,x);

            low[x]=Min(low[u],low[x]);

        }

        else if(insta[u])

            low[x]=Min(low[x],dfn[u]);

        k=next[k][0];

    }

    if(low[x]==dfn[x])

    {

        ++cnt;

        while(19260817)

        {

            int y=sta[top--];

            id[y]=cnt;

            if(x==y)

                break;

        }

    }

    return;

}

inline void rebuild()

{

    tot=0;

    for(register int i=1;i<=m;++i)

        if(id[xx[i]]!=id[yy[i]])

            add(id[xx[i]],id[yy[i]],1);

}

inline void DFS2(register int son,register int fa)

{

    dep[son]=dep[fa]+1;

    p[son][0]=fa;

    for(register int i=first[son][1];i;i=next[i][1])

        if(to[i][1]!=fa)

            DFS2(to[i][1],son);

}

inline int LCA(register int a,register int b)

{

    if(a==b)

        return a;

    if(dep[a]>dep[b])

        Swap(a,b);

    for(register int i=20;i>=0;--i)

        if(dep[p[b][i]]>=dep[a])

            b=p[b][i];

    if(a==b)

        return a;

    for(register int i=20;i>=0;--i)

        if(p[a][i]!=p[b][i])

            a=p[a][i],b=p[b][i];

    return p[a][0];

}

int main()

{

    n=read(),m=read();

    for(register int i=1;i<=m;++i)

    {

        xx[i]=read(),yy[i]=read();

        add(xx[i],yy[i],0);

    }

    for(register int i=1;i<=n;++i)

        if(!dfn[i])

            DFS(i,0);

    rebuild();

    DFS2(1,0);

    for(register int i=1;i<=20;++i)

        for(register int j=1;j<=cnt;++j)

            p[j][i]=p[p[j][i-1]][i-1];

    q=read();

    while(q--)

    {

        int a=read(),b=read();

        a=id[a],b=id[b];

        int lca=LCA(a,b),ans=0;

        ans=dep[a]+dep[b]-(dep[lca]<<1)+1;

        print(ans);

    }

    return 0;

}