南外 Day 5

今天打图连通
T1 强连通分量，tarjan一下
T2 干了一上午才过，spfa正反图+tarjan
T3 不知道为什么WA好几次，但最终A了
T4 一会RE一会WA
T5 就边双一下
T6 点双 写炸了————
T7 8 9 问其他DALAO hh
very 简略
so
随便贴串边双代码（有注释，禁止copy

#include<bits/stdc++.h>
//方便使用 
#define fup(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define fdown(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
using namespace std;
const int N=1e5+10,M=N<<3,Fd=18;//定义大小的常量 
//一堆变量 
int n,m,s;
int head[N],nxt[M],tot;
int e[M],id[N];
int headbfs[N];
int dfn[N],low[N];
int times;
int stk[N],top;
int cnts;
int dep[N];
int fa[N][Fd];
int q[N];
void add(int *head,int a,int b)//插入 
{
    e[tot]=b;
    nxt[tot]=head[a];
    head[a]=tot++;
}
void tarjan(int x,int from)//模板 tarjan 随便打 
{
    dfn[x]=low[x]=++times;
    stk[++top]=x;
    for(int i=head[x];i!=-1;i=nxt[i])
    {
        int y=e[i];
        if(!dfn[y])
        {
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
        }
        else if(i!=(from^1))
            low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x])
    {
        cnts++;
        int y;
        do
        {
            y=stk[top--];
            id[y]=cnts;
        }while(x!=y);
    }
}
void bfs()//宽搜，找就对了 
{
    int ahead=0,atail=0;
    q[0]=1;
    dep[1]=1;
    while(ahead<=atail)
    {
        int nxtnode=q[ahead++];
        for(int i=headbfs[nxtnode];i!=-1;i=nxt[i])
        {
            int j=e[i];
            if(dep[j]) continue;
            dep[j]=dep[nxtnode]+1;
            fa[j][0]=nxtnode;
            fup(k,1,Fd-1)
                fa[j][k]=fa[fa[j][k-1]][k-1];
            q[++atail]=j;
        }
    }
}
int lca(int a,int b)//做一下询问的 a,b 的 LCA 
{
    if(dep[a]<dep[b]) swap(a,b);
    fdown(i,Fd-1,0)
        if(dep[fa[a][i]]>=dep[b])
            a=fa[a][i];
    if(a==b) return a;
    fdown(i,Fd-1,0)
        if(fa[a][i]!=fa[b][i])
        {
            a=fa[a][i];
            b=fa[b][i];
        }
    return fa[a][0];
}
void init()//初始化，全是 -1 
{
    memset(head,-1,sizeof head );
    memset(headbfs,-1,sizeof headbfs );
}
signed main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    scanf("%d%d",&n,&m);
    init();
    fup(i,1,m)//读入并建图 
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(head,a,b);
        add(head,b,a);
    }
    tarjan(1,-1);//日常 tarjan 
    fup(i,1,n)
        for(int j=head[i];j!=-1;j=nxt[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a!=b)
            {
                add(headbfs,a,b);
                add(headbfs,b,a);
            }
        }
    bfs();//做下 bfs 
    scanf("%d",&s);//读入询问 
    fup(i,1,s)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        a=id[a],b=id[b];
        int gf=lca(a,b);
        printf("%d\n",dep[a]+dep[b]-2*dep[gf]);//lca求祖先得答案 
    }
    return 0;
}

明天和zgc出去玩~