POJ 3694 Network 无向图双联通+LCA

一开始题目没看清楚，以为是增加那条边后还有多少桥，所以就当做是无向图tarjan缩点后建树，然后求u，v的最近公共祖先，一直wa。

后来再看题目后才发现边放上去后不会拿下来了，即增加i条边后桥的数量。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

const int maxn = 100100;

const int maxm =  200100;

struct node{

    int v,next;

}edge[maxm*2];

int head[maxn],low[maxn],dfn[maxn],fa[maxn],stack[maxn],in[maxn],vis[maxm*2];

int res[maxn][2],depth[maxn],father[maxn];

int n,m,id,clock,top,total,num,q;

void add_edge(int u,int v){

    edge[id].v = v;edge[id].next = head[u];head[u] = id++;

    edge[id].v = u;edge[id].next = head[v];head[v] = id++;

}

void init(){

	memset(head,-1,sizeof(head));

    memset(dfn,0,sizeof(dfn));

	memset(fa,0,sizeof(fa));

    memset(vis,0,sizeof(vis));

    id = total = top = clock = num = 0;

    int u,v;

    while( m-- ){

        scanf("%d%d",&u,&v);

        add_edge(u,v);

    }

}

void tarjan(int u){

    low[u] = dfn[u] = ++clock;

    stack[top++] = u;in[u] = 1;

    for(int id = head[u]; id != -1; id = edge[id].next){

        if( vis[id] )continue;//如果边以及走过，则不能再走了

        vis[id] = vis[id^1] = 1;//标记边已经走过

        int v = edge[id].v;

        if(!dfn[v]){

            tarjan(v);

            if( dfn[u] < low[v])

            {//将桥两端的顶点保存下来

                res[total][0] = u;

                res[total++][1] = v;

            }

            low[u] = low[v] < low[u] ? low[v] : low[u];

        }

        else if(in[v] && low[u] > dfn[v])low[u] = dfn[v];

    }

    if( dfn[u] == low[u]){

         ++num;//缩点

        do{

            int v = stack[--top];

            fa[v] = num;

            in[v] = 0;

        }while( u != stack[top]);

    }

}

void dfs(int u,int dep){//确定个顶点的深度，以及其父亲节点

    depth[u] = dep;

    vis[u] = 1;

    for(int id= head[u]; id != -1; id = edge[id].next){

        int v = edge[id].v;

        if(vis[v])continue;

        father[v] = u;

        dfs(v,dep+1);

    }

}

int find(int x,int y){//递归找x，y的最近公共祖先

    if(x == y)return x;

   if(depth[x] > depth[y] )

   {

        if(!vis[x])total --;//当x所连的点为桥时，桥的数量减1

        vis[x] = 1;

        return find(father[x],y);

   }

   if(!vis[y])total --;

        vis[y] = 1;

    return find(x,father[y]);

}

void solve(){

	int i;

    tarjan(1);

    int u,v;

	memset(head,-1,sizeof(head));

	id= 0;

    for( i = 0 ; i < total; i++){//建树

        u = fa[res[i][0]], v = fa[res[i][1]];

        add_edge(u,v);

    }

    memset(vis,0,sizeof(vis));

    father[1] = 1;

    dfs(1,1);

}

int main(){

    int u,v;

  // freopen("in.txt","r",stdin);

    int cas = 1;

    while(~scanf("%d%d",&n,&m),n&&m){

        init();

        solve();

		scanf("%d",&q);

        printf("Case %d:\n",cas++);

        memset(vis,0,sizeof(vis));

        for(int i = 1; i <= q; i ++)

        {

			scanf("%d%d",&u,&v);

			u = fa[u];v = fa[v];

			find(u,v);

			printf("%d\n",total);

        }

        puts("");

    }

    return 0;

}