POJ 3694 Network

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

题意:给定无向图,给定若干询问,每个询问加入一条边,问加入该边后图中桥的数目。

思路:首先先缩点成一棵树,那么每加入一条边就相当于形成了一个环,我们就是要找这个环然后再把他们缩成一个点。找环中的边的过程实际就是找最近公共祖先的过程,向上爬的过程中遇到的所有边都不再是桥。集合并起来很自然的想到用并查集动态维护,而缩点过程我们也可以在dfs求桥的同时用并查集维护同一边双连通分量的点。对于每个询问在两个点向上爬的时候判断该点是否与父节点在同一集合中,若不是,说明连边为桥,删去,并将该点与其父节点并起来。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
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 x=_f?-x:x;
}
int n,m,u,v,Q,cnt,dfs_clock,fa[maxn],anc[maxn],pre[maxn],low[maxn];
vector<int>G[maxn];
int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
bool mix(int x,int y){
    int tx=Find(x),ty=Find(y);
    if (tx!=ty){
        fa[tx]=ty;
        return true;
    }
    return false;
}
int dfs1(int u,int f){
    anc[u]=f==-1?1:f;
    int lowu=pre[u]=++dfs_clock;
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (!pre[v]){
            int lowv=dfs1(v,u);
            lowu=min(lowu,lowv);
            if (lowv>pre[u]){
                cnt++;
            }
            else mix(v,u);
        }
        else if (pre[v]<pre[u] && v!=f) lowu=min(lowu,pre[v]);
    }
    return low[u]=lowu;
}
void find_bcc(){
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int i=1;i<=n;i++) if (!pre[i]) dfs1(i,-1);
}
void init(){
    cnt=dfs_clock=0;
    memset(pre,0,sizeof(pre));
    for (int i=1;i<=n;i++) G[i].clear();
}
void lca(int u,int v){
    if (pre[u]<pre[v]) swap(u,v);
    while (pre[u]>pre[v]){
        if (mix(u,anc[u])) cnt--;
        u=anc[u];
    }
    while (u!=v){
        if (mix(u,anc[u])) cnt--;
        if (mix(v,anc[v])) cnt--;
        u=anc[u];
        v=anc[v];
    }
}
int main(){
    int cas=1;
    while (~scanf("%d%d",&n,&m)&&n+m){
        init();
        for (int i=1;i<=m;i++){
            read(u),read(v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        find_bcc();
        printf("Case %d:\n",cas++);
        for (read(Q);Q--;){
            read(u),read(v);
            lca(u,v);
            printf("%d\n",cnt);
        }
        puts("");
    }
    return 0;
}

发表评论

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