POJ 3694 Network

题目链接http://poj.org/problem?id=3694

题意:给定一张无向图,Q个询问,每次询问加了边(x,y)后整张图桥的数量。

思路:边双连通分量缩点后桥的数量就是树的边数,每次询问的时候暴力LCA往上跳同时用并查集进行缩点即可。

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return _f?-x:x;
}
const int N=100000+10,M=200000+10;
int n,m,u,v,i,Q,cnt,tot,tot2,dfs_clock,id[N],dfn[N],low[N];
int head[N],nxt[M*2],to[M*2],head2[N],nxt2[M*2],to2[M*2];
int p[N],fa[N],dep[N];
bool bridge[M*2];
void init(){
    memset(head,-1,sizeof(head));
    memset(head2,-1,sizeof(head2));
    memset(bridge,0,sizeof(bridge));
    memset(dfn,0,sizeof(dfn));
    memset(id,0,sizeof(id));
    tot=tot2=-1;
    cnt=dfs_clock=0;
}
void addedge(int u,int v){to[++tot]=v,nxt[tot]=head[u],head[u]=tot;}
void addedge2(int u,int v){to2[++tot2]=v,nxt2[tot2]=head2[u],head2[u]=tot2;}
void umin(int&a,int b){if(a>b)a=b;}
void tarjan(int u,int in_edge){
    dfn[u]=low[u]=++dfs_clock;
    for (int i=head[u];~i;i=nxt[i]){
        int v=to[i];
        if (!dfn[v]){
            tarjan(v,i);
            umin(low[u],low[v]);
            if (low[v]>dfn[u]){
                bridge[i]=bridge[i^1]=true;
            }
        }
        else if (i!=(in_edge^1)) umin(low[u],dfn[v]);
    }
}
void dfs(int u){
    id[u]=cnt;
    for (int i=head[u];~i;i=nxt[i]){
        int v=to[i];
        if (id[v] || bridge[i]) continue;
        dfs(v);
    }
}
void dfs(int u,int f){
    p[u]=f;
    dep[u]=f?dep[f]+1:0;
    for (int i=head2[u];~i;i=nxt2[i]){
        int v=to2[i];
        if (v==f) continue;
        dfs(v,u);
    }
}
int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
void Merge(int x){
    int y=Find(p[x]);
    x=Find(x);
    if (x^y) cnt--,fa[x]=y;
}
void update(int u,int v){
    while (dep[u]>dep[v]) Merge(u),u=p[u];
    while (dep[u]<dep[v]) Merge(v),v=p[v];
    while (u!=v){
        Merge(u);
        Merge(v);
        u=p[u];
        v=p[v];
    }
}
int main(){
    int cas=1;
    while (~scanf("%d%d",&n,&m)&&(n||m)){
        init();
        for (i=1;i<=m;i++){
            read(u),read(v);
            addedge(u,v);
            addedge(v,u);
        }
        tarjan(1,0);
        for (i=1;i<=n;i++){
            if (!id[i]) ++cnt,dfs(i);
        }
        for (i=0;i<=tot;i++){
            int x=to[i],y=to[i^1];
            if (id[x]==id[y]) continue;
            addedge2(id[x],id[y]);
        }
        for (i=1;i<=cnt;i++) fa[i]=i;
        dfs(1,0),cnt--;
        printf("Case %d:\n",cas++);
        for (read(Q);Q--;){
            read(u),read(v);
            if (id[u]==id[v]) printf("%d\n",cnt);
            else{
                int tx=Find(id[u]),ty=Find(id[v]);
                if (tx^ty) update(id[u],id[v]);
                printf("%d\n",cnt);
            }
        }
        puts("");
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注