洛谷P2783 有机化学之神偶尔会作弊

我刚做完这题就掉紫了

这道题的题意非常的显然，所以我们只要直接按照题意做一遍就好了。

最后求两点之间距离的时候，求一个$LCA$即可，答案就是$d[a]+d[b]-2* d[lca(a,b)]+1$

所以这道题就做完了(雾

边双联通分量有有两种方法，其中一种是求出所有割边，然后依次删去。这样剩下的图就被分成了很多单独的部分，每一个部分就是一个$e-DCC$

另一种方法则和有向图的缩点相似，我们用一个栈记录搜索树上的点，当$low[x]=dfn[x]$的时候将$stack$里的点依次退出，一直退到$x$，我们便求出了一个$e-DCC$

最下方题面里说两个点不删去所以当我们$tarjan$的时候遇到$x$的父亲就直接$continue$,按这个思路法二可以过。

但是法一即使加上这个判断也过不了，所以还是不写法一比较好(雾

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define N 100500
#define M 500500
int stack[N],top,ttt,n,m,head[N],num=1,dfn[N],low[N],cnt,bridge[M],he[N],sy[N],numm,t,f[100050][50],d[N];
queue<int> q;
struct node
{
    int next,to;
}edge[M*2],tu[M*2];
void addedge(int u,int v)
{
    edge[++num]=(node){head[u],v};
    head[u]=num;
}
void newaddedge(int u,int v)
{
    tu[++numm]=(node){he[u],v};
    he[u]=numm;
}
void tarjan(int x,int fa)
{
    low[x]=dfn[x]=++cnt;
    stack[++top]=x;
    for(int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa)continue;
        if(!dfn[v])
        {
            tarjan(v,x);
            low[x]=min(low[x],low[v]);
        }
        else low[x]=min(low[x],dfn[v]);
    }
    if(low[x]==dfn[x])
    {
        sy[x]=++ttt;
        while(stack[top]!=x)sy[stack[top]]=ttt,top--;
        top--;
    }
}
void jb(int x)
{
    sy[x]=cnt;
    for(int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(bridge[i]||sy[v])continue;
        jb(v);
    }
}
void bfs()
{
    q.push(1);
    d[1]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=he[u];i;i=tu[i].next)
        {
            int v=tu[i].to;
            if(d[v])continue;
            d[v]=d[u]+1;
            f[v][0]=u;
            for(int k=1;k<=t;k++)f[v][k]=f[f[v][k-1]][k-1];
            q.push(v);
        }
    }
}
int lca(int a,int b)
{
    if(d[a]<d[b])swap(a,b);
    for(int i=t;i>=0;i--)if(d[f[a][i]]>=d[b])a=f[a][i];
    if(a==b)return a;
    for(int i=t;i>=0;i--)if(f[a][i]!=f[b][i])a=f[a][i],b=f[b][i];
    return f[a][0];
}
void xs(int shu)
{
    int answer[500000],kkk=0;
    while(shu)
    {
        answer[++kkk]=shu%2;
        shu/=2;
    }
    for(int i=kkk;i>=1;i--)printf("%d",answer[i]);
    printf("\n");
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(u,v);addedge(v,u);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,0);
    cnt=0;
   // for(int i=1;i<=n;i++)if(!sy[i]){++cnt;jb(i);}
    for(int i=2;i<=num;i++)if(sy[edge[i].to]!=sy[edge[i^1].to])newaddedge(sy[edge[i].to],sy[edge[i^1].to]);
    t=32;
    bfs();
    int tot;
    scanf("%d",&tot);
    for(int i=1;i<=tot;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        a=sy[a];b=sy[b];
        int lcab=lca(a,b);
        xs(d[a]+d[b]-2*d[lcab]+1);
    }
    return 0;
}