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

2018-11-08 12:35:51


又一道黑题

思路:

显然的缩点+树剖/倍增求lca

由于是无向图,缩点时写法略有变化,即一个点和他的父亲不能构成强连通分量

缩点就这么写:(码风略丑)

void dfs(int u,int fa){
    vis[u]=1;
    dfn[u]=low[u]=++ti;
    st[++sttop]=u;
    inst[u]=1;
    for(int i=oldhead[u];i;i=nod[i].next){
        int d=nod[i].v;
        if(d==fa)continue;
        if(!vis[d]){
            dfs(d,u);
            low[u]=min(low[u],low[d]);
        }
        else if(inst[d])low[u]=min(low[d],low[u]);
    }
    if(dfn[u]==low[u]){
        int now;
        taj++;
        do{
            now=st[sttop--];
            inst[now]=0;
            Belong[now]=taj;
        }while(now!=u);
    }
}

还有这奇怪的输出格式:

inline int out(int n){//输出n的二进制表示
    int o=log2(n);
    for(;o>=0;o--){
        if((1<<o)<=n){
            n-=(1<<o);
            printf("1");
        }
        else printf("0");
    }
    printf("\n");
}

完整代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
int toop,cnt;
int oldhead[11010];
int head[10101];
struct Node{
    int v;
    int next;
}nod[101010],node[101010];
inline void ad(int u,int v){
    nod[++toop].v=v;
    nod[toop].next=oldhead[u];
    oldhead[u]=toop;
}//旧图 
inline void addedge(int u,int v){
    node[++cnt].v=v;
    node[cnt].next=head[u];
    head[u]=cnt;
}//新图 
inline void add(int u,int v){
    ad(u,v);
    ad(v,u);
}//旧图
inline void newadd(int u,int v){
    addedge(u,v);
    addedge(v,u);
}//新图 
int n,m;
int Belong[11010];
int vis[11010];
bool inst[10505];
int st[10101];
int sttop;
int taj;
int dfn[10101],low[10101],ti;
void dfs(int u,int fa){
    vis[u]=1;
    dfn[u]=low[u]=++ti;
    st[++sttop]=u;
    inst[u]=1;
    for(int i=oldhead[u];i;i=nod[i].next){
        int d=nod[i].v;
        if(d==fa)continue;
        if(!vis[d]){
            dfs(d,u);
            low[u]=min(low[u],low[d]);
        }
        else if(inst[d])low[u]=min(low[d],low[u]);
    }
    if(dfn[u]==low[u]){
        int now;
        taj++;
        do{
            now=st[sttop--];
            inst[now]=0;
            Belong[now]=taj;
        }while(now!=u);
    }
}
void sd(){
    int i,j;
    for(i=1;i<=n;i++)if(!vis[i])dfs(i,i);
    for(i=1;i<=n;i++){
        for(j=oldhead[i];j;j=nod[j].next){
            int d=nod[j].v;
            if(Belong[i]!=Belong[d]) newadd(Belong[i],Belong[d]);
        }
    }
}
int dep[10101],siz[10101],fa[10101],son[10101],top[10101];
void dfs1(int u){
    siz[u]=1;
    for(int i=head[u];i;i=node[i].next){
        int d=node[i].v;
        if(fa[u]!=d){
            fa[d]=u;
            dep[d]=dep[u]+1;
            dfs1(d);
            siz[u]+=siz[d];
            if(siz[d]>siz[son[u]])son[u]=d;
        }
    }
}
void dfs2(int u,int tp){
    top[u]=tp;
    if(son[u])dfs2(son[u],tp);
    for(int i=head[u];i;i=node[i].next){
        int d=node[i].v;
        if(fa[u]!=d&&son[u]!=d)dfs2(d,d);
    }
}
inline int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]])u=fa[top[u]];
        else v=fa[top[v]];
    }
    return dep[u]>dep[v]?v:u;
}
inline int out(int n){
    int o=log2(n);
    for(;o>=0;o--){
        if((1<<o)<=n){
            n-=(1<<o);
            printf("1");
        }
        else printf("0");
    }
    printf("\n");
}
int main(){
    n=Read(),m=Read();
    register int i;
    int u,v;
    for(i=1;i<=m;i++)u=Read(),v=Read(),ad(u,v);
    sd();
    dep[1]=1;
    dfs1(1);
    dfs2(1,1);
    int q;
    q=Read();
    while(q--){
        u=Read(),v=Read();
        u=Belong[u];
        v=Belong[v];
        out(dep[u]+dep[v]-2*dep[lca(u,v)]+1);
    }
    return 0;
}

求赞