POJ 3694:桥

题意：给N个点，M条边，随后加入Q条边，边可能会重复，对于每一次加边，问图中剩余桥的数量

思路：简单的做法就是建图后用tarjan求出桥的数量cnt，再对于每次新加的边u,v，用总数cnt减去所成环（有的话）里桥的数量

#include"cstdio"
#include"queue"
#include"cmath"
#include"stack"
#include"iostream"
#include"algorithm"
#include"cstring"
#include"queue"
#include"map"
#include"set"
#include"vector"
#define ll long long
#define mems(a,b) memset(a,b,sizeof(a))
#define ls pos<<1
#define rs pos<<1|1
#define max(a,b) (a)>(b)?(a):(b)
using namespace std;
const int MAXE = 400050;
const int MAXN = 1e5+5;
const int INF = 0x3f3f3f3f;

int n,q,m,p=1;
int dfn[MAXN],low[MAXN],fa[MAXN],id,cnt,tot;
int dep[MAXN],brige[MAXN],first[MAXE];
struct node{
    int e,next;
    node(){}
    node(int a,int b):e(a),next(b){};
}edge[MAXE];

void init(){
    tot=0;
    id=0;
    cnt=0;
    mems(dfn,0);
    mems(first,-1);
}

void addedge(int u,int v){
    edge[tot]=node(v,first[u]);
    first[u]=tot++;
    edge[tot]=node(u,first[v]);
    first[v]=tot++;
}

void tarjan(int u,int pre){
    fa[u]=pre;
    dep[u]=dep[pre]+1;
    dfn[u]=low[u]=++id;
    for(int i=first[u];i!=-1;i=edge[i].next){
        int v=edge[i].e;
        if(v==pre) continue;
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]) brige[v]=1,cnt++;
        }
        else low[u]=min(low[u],dfn[v]);
    }
}

void lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    while(dep[u]!=dep[v]){
        if(brige[u]){
            cnt--;
            brige[u]=0;
        }
        u=fa[u];
    }
    while(u!=v){
        if(brige[u]){
            cnt--;
            brige[u]=0;
        }
        if(brige[v]){
            cnt--;
            brige[v]=0;
        }
        u=fa[u];
        v=fa[v];
    }
}

int main(){
    //freopen("in.txt","r",stdin);
    while(~scanf("%d%d",&n,&m)){
        if(!n&&!m) break;
        init();
        int u,v;
        for(int i=0;i<m;i++){
            scanf("%d%d",&u,&v);
            addedge(u,v);
        }
        dep[0]=0;
        tarjan(1,0);
        printf("Case %d:
",p++);
        scanf("%d",&q);
        for(int i=0;i<q;i++){
            scanf("%d%d",&u,&v);
            lca(u,v);
            printf("%d
",cnt);
        }
        printf("
");
    }
    return 0;
}