题解 UVA1464 【Traffic Real Time Query System】 点双缩点+LCA

· · 题解

UVA1464 Traffic Real Time Query System

我终于AC了呜呜呜

题面

一个城市有 n 个路口，m 条无向公路。现在要求从第 S 条路到第 T 条路必须经过的点有几个。

题解

缩点之后建新图，会发现图一定是

连通块---割顶---连通块---……---连通块

所以答案就是

(dep[u]+dep[v]-dep[LCA(u,v)]+1)/2

感性理解一下

注意点

Code

给个代码对照一下吧，调代码没有一个参照好累好累

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm> 
#define re register
#define il inline
#define ll long long
using namespace std;

il int read(){
    int s=0,f=0;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-'),c=getchar();
    while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+(c^'0'),c=getchar();
    return f?-s:s;
}

const int N=2e4+5,M=1e5+5;
int n,m,q;
struct E{
    int next,to;
    bool fl;
};

int dfn[N],low[N],dfs_tim,st[N],top,dccnum,cut[N],cutnum,ebelong[M]; //点双  
struct G{
    E e[M<<1];
    int head[N],cnt;
    il void add_edge(int u,int v){
        e[cnt].next=head[u],e[cnt].to=v,head[u]=cnt++;
    }
    il void init(){
        while(cnt) e[cnt].fl=0,cnt--;
        e[0].fl=0;
        memset(head,-1,sizeof(head));
    }
}g,g2;

void tarjan(int u,int rt){
    dfn[u]=low[u]=++dfs_tim;
    int son=0;
    for(re int i=g.head[u];~i;i=g.e[i].next){
        int v=g.e[i].to;
        if(g.e[i].fl) continue;
        g.e[i].fl=g.e[i^1].fl=1; 
        st[++top]=(i>>1);
        if(!dfn[v]){
            son++;
            tarjan(v,rt);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                if(u!=rt) cut[u]=1;
                ++dccnum;
                while(1){
                    int x=st[top];
                    ebelong[x]=dccnum;
                    top--;
                    if(x==(i>>1)) break;
                }
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
    if(u==rt&&son>=2) cut[u]=1;
}

int f[N][16],dep[N],lg2[N];
int vis[N],tot;
void dfs(int u,int fa){
    vis[u]=tot;
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(re int i=1;(1<<i)<=dep[u];++i)
        if(f[u][i-1]) f[u][i]=f[f[u][i-1]][i-1];
    for(re int i=g2.head[u];~i;i=g2.e[i].next){
        int v=g2.e[i].to;
        if(v!=fa) dfs(v,u);
    }
}
il int LCA(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) 
        x=f[x][lg2[dep[x]-dep[y]]];
    if(x==y) return x;
    for(re int i=lg2[dep[x]];i>=0;--i)
        if(f[x][i]&&f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}

int main(){
    while(scanf("%d%d",&n,&m),n){
        memset(dfn,0,sizeof(dfn));
        memset(vis,0,sizeof(vis));
        memset(cut,0,sizeof(cut));
        memset(f,0,sizeof(f));
        memset(ebelong,0,sizeof(ebelong));
        dfs_tim=dccnum=top=tot=cutnum=0;
        g.init(),g2.init();

        for(re int i=1,u,v;i<=m;++i) u=read(),v=read(),g.add_edge(u,v),g.add_edge(v,u);

        for(re int i=1;i<=n;++i) 
            if(!dfn[i]) tarjan(i,i);
        for(re int u=1;u<=n;++u) if(cut[u]){
            cut[u]=(++cutnum)+dccnum;
            ++tot;
            for(re int i=g.head[u];~i;i=g.e[i].next){
                int v=ebelong[i>>1];
                if(vis[v]!=tot) vis[v]=tot,g2.add_edge(v,cut[u]),g2.add_edge(cut[u],v);
            }
        }

        lg2[0]=-1;
        for(re int i=1;i<=dccnum+cutnum;++i) lg2[i]=lg2[i>>1]+1;
        ++tot;dep[0]=-1;
        for(re int i=1;i<=dccnum+cutnum;++i) if(vis[i]!=tot) dfs(i,0);

        q=read();
        for(re int i=1,u,v;i<=q;++i)
            u=ebelong[read()-1],v=ebelong[read()-1],
            printf("%d\n",(dep[u]+dep[v]-2*dep[LCA(u,v)]+1)/2);
    }
    return 0;
}