poj 3694 Network

kgxw0430 2019-01-09 原文

　　题意：先给定一张无向连通图，每次有一个询问，让你求新建一条边（x，y）之后图中还有多少条割边。

　　如果你是打算每次重新跑一边tarjan的话，先善良的告诉你，N的范围是1e5，Q是1000。那么就另想招吧。有没有想到缩点呢？我们对图求一下e—DCC，然后缩点建一张新图，首先，新图是一棵树。在没有添加边的时候，答案就是树的边数。每次如果添加了（x，y），那么从c【x】和c【y】向上爬，直到它们的lca P，这中间的边如果是割边，那么现在都是非割边，都依次标记，然后答案减1；这样的话，复杂度是O（M+N*Q），呵呵因为数据水的缘故，这样是可以A的。

　　求lca的过程可以使用并查集的思路，在标记的同时进行路径压缩。就变成log的了

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=4e5+10;
int q,n,m,tot,num,cnt,tc,ans,low[N],dfn[N],lin[N],c[N],ver[M],Next[M],cut[M],vc[M],nc[M],lc[N];
int dep[N],fa[N],flag[N];
void add(int x,int y){
    ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;
}
void addc(int x,int y){
    vc[++tc]=y;nc[tot]=lc[x];lc[x]=tc;
}
void tarjan(int x,int in_edge){
    dfn[x]=low[x]=++num;
    for(int i=lin[x];i;i=Next[i]){
        int y=ver[i];
        if(!dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);
            if(dfn[x]<low[y]) cut[i]=cut[i^1]=1;
        }else if(i!=(in_edge^1)) low[x]=min(low[x],dfn[y]);
    }
}
void dfs(int x){
    c[x]=cnt;
    for(int i=lin[x];i;i=Next[i]){
        int y=ver[i];
        if(c[y]||cut[i]) continue;
        dfs(y);
    }
}
void dfss(int x,int f){
    dep[x]=dep[f]+1;fa[x]=f;
    for(int i=lc[x];i;i=nc[i]){
        int y=vc[i];
        if(y==f) continue;
        dfss(y,x);
    }
}
void lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]!=dep[y]){
        if(!flag[x]) ans--,flag[x]=1;
        x=fa[x];
    }
    while(x!=y){
        if(!flag[x]) ans--,flag[x]=1;
        if(!flag[y]) ans--,flag[y]=1;
        x=fa[x],y=fa[y];
    }
}
int main(){
    while(scanf("%d %d",&n,&m)){
        if(!n&&!m) break;
        memset(lin,0,sizeof(lin));
        memset(lc,0,sizeof(lc));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(c,0,sizeof(c));
        memset(flag,0,sizeof(flag));
        memset(fa,0,sizeof(fa));
        tot=1;
        for(int i=1;i<=m;++i){
            int x,y;scanf("%d%d",&x,&y);
            add(x,y);add(y,x);
        }
        for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,0);
        cnt=0;
        for(int i=1;i<=n;++i){
            if(!c[i])
                cnt++,dfs(i);
        }
        tc=1;
        for(int i=2;i<=tot;++i){
            int x=ver[i^1],y=ver[i];
            if(c[x]==c[y]) continue;
            addc(c[x],c[y]);
        }
        ans=tc-1;
        dfss(1,0);
        scanf("%d",&q);
        for(int i=1;i<=q;++i){
            int x,y;scanf("%d%d",&x,&y);
            x=c[x],y=c[y];
            lca(x,y);
            printf("%d\n",ans);
        }
    }
    return 0;
}