题目背景

XS中学化学竞赛组教练是一个酷爱炉石的人。

有一天他一边搓炉石一边监考，而你作为一个信息竞赛的大神也来凑热闹。

然而你的化竞基友却向你求助了。

“第1354题怎么做”<--手语他问道。

题目描述

你翻到那一题：给定一个烃，只含有单键（给初中生的一个理解性解释：就是一堆碳用横线连起来，横线都是单条的）。

然后炎魔之王拉格纳罗斯用他的火焰净化了一切环（？？？）。所有的环状碳都变成了一个碳。如图所示。

然后指定多组碳，求出它们之间总共有多少碳。如图所示（和上图没有关系）。

但是因为在考试，所以你只能把这个答案用手语告诉你的基友。你决定用二进制来表示最后的答案。如图所示（不要在意，和题目没有什么没关系）。

输入格式

第一行两个整数n,m.表示有n个点，m根键

接下来m行每行两个整数u，v表示u号碳和v号碳有一根键

接下来一个整数tot表示询问次数

接下来tot行每行两个整数，a,b表示询问的两个碳的编号

输出格式

共tot行

每行一个二进制数

说明/提示

1<n<=10000,1<m<=50000

（两个碳不成环）

求边联通分量

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=2e5+10,M=2e6+10;

int next[M],head[N],go[M],tot;

inline void add(int u,int v){

	next[++tot]=head[u];head[u]=tot;go[tot]=v;

}

int dep[N];

int dfn[N],low[N],num,st[N],top;

int n,m,co[N],col,fa[N][16];

int vis[N],xx[M],yy[M],bridge[M];

inline void tarjan(int x,int f){//除了父节点判断，几乎一模一样哦

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

    st[++top]=x;vis[x]=1;

    for(int i=head[x];i;i=next[i]){

        int y=go[i];

        if(y==f)continue;//就这个地方不同

        if(!dfn[y]){

            tarjan(y,x);

            low[x]=min(low[x],low[y]);

        }

        else if(vis[y])low[x]=min(low[x],dfn[y]);

    }

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

        ++col;

        while(st[top+1]!=x){

            int y=st[top--];

            co[y]=col;

        }

    }

}

inline void dfs2(int x,int f,int deep){

    fa[x][0]=f;dep[x]=deep;

    for(int i=1;i<=15;++i)

    fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=next[i]){

        int y=go[i];

        if(y==f)continue;

        dfs2(y,x,deep+1);

    }

}

inline int lca(int x,int y){

    if(dep[x]<dep[y])swap(x,y);

    for(int i=15;i>=0;i--)

    if(dep[fa[x][i]]>=dep[y])x=fa[x][i];

    if(x==y)return x;

    for(int i=15;i>=0;i--)

    if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

    return fa[x][0];

}

inline void print(int x){

    if(!x)return;

    print(x/2);

    putchar((char)((x&1)+'0'));

}

int main(){

    cin>>n>>m;

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

        cin>>xx[i]>>yy[i];

        if(xx[i]>yy[i])

		swap(xx[i],yy[i]);

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

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

    }

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

    if(!dfn[i])tarjan(i,i);

    tot=1;

    memset(head,0,sizeof head);

    memset(next,0,sizeof next);

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

    if(co[xx[i]]!=co[yy[i]]){

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

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

    }

    dfs2(1,0,1);

    int q,xzz,yyb;

    cin>>q;

    while(q--){

        cin>>xzz>>yyb;

        xzz=co[xzz];yyb=co[yyb];

        int zsy=lca(xzz,yyb),sum;

        sum=(dep[xzz]-dep[zsy]+1)+(dep[yyb]-dep[zsy]);

        print(sum);

		puts("");

    }

}

巴特西

luogu P2783 有机化学之神偶尔会做作弊 |Tarjan+LCA