poj 3694 无向图求桥+lca

题意抽象为：

给一个无向图和一些询问

对于每一次询问：

每次询问都会在图上增加一条边

对于每一次询问输出此时图上桥的个数。

桥的定义：删除该边后原图变为多个连通块。

数据规模：点数N(1 ≤ N ≤ 100,000) ，边数M(N - 1 ≤ M ≤ 200,000)，询问数Q ( 1 ≤ Q ≤ 1,000)

先跑一遍tarjan，对边双连通分枝缩一下点。

再维护lca即可。

AC代码：

#include<cstdio>

#include<cstring>

#include<queue>

#define rep(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

const int MAXV=;

const int MAXE=;

int DFN[MAXV],low[MAXV],par[MAXV],label[MAXV];

int pointer[MAXV];

int tot,cnt,m,n,Bcnt,ans;

vector<int> graph[MAXV];

struct Edge

{

    int to,next;

    bool vis;

    Edge() {}

    Edge(int b,int nxt,int flag) {to=b,next=nxt,vis=flag;}

}edge[MAXE];

inline void addedge(int a,int b)

{

    edge[tot]=Edge(b,pointer[a],);

    pointer[a]=tot++;

    edge[tot]=Edge(a,pointer[b],);

    pointer[b]=tot++;

}

void init()

{

    tot=;

    cnt=;Bcnt=;

    memset(pointer,-,sizeof(pointer));

    memset(label,,sizeof(label));

    memset(DFN,,sizeof(DFN));

}

void tarjan(int u,int pre)

{

    DFN[u]=low[u]=++cnt;

    for(int j=pointer[u];j!=-;j=edge[j].next)

    {

        int v=edge[j].to;

        if(edge[j].vis) continue;

        edge[j].vis=edge[j^].vis=;

        if(!DFN[v])

        {

            par[v]=j;

            tarjan(v,u);

            if(low[v]<low[u]) low[u]=low[v];

        }

        else if(low[u]>DFN[v]) low[u]=DFN[v];

    }

}

void part(int u)

{

    label[u]=Bcnt;

    for(int j=pointer[u];j!=-;j=edge[j].next)

    {

        int v=edge[j].to;

        if(!label[v]&&edge[j].vis) part(v);

    }

}

int dep[MAXV];

int father[MAXV],a[MAXV];

void lca_bfs(int S)

{

    rep(i,,Bcnt) dep[i]=-;

    queue<int>q;

    dep[S]=;

    q.push(S);

    father[S]=S;

    while(!q.empty())

    {

        int u=q.front();q.pop();

        for(int i=;i<graph[u].size();++i)

        {

            int v=graph[u][i];

            if(dep[v]==-)

            {

                dep[v]=dep[u]+;

                a[v]=;

                father[v]=u;

                q.push(v);

            }

        }

    }

}

void lca(int u,int v)

{

    if(dep[u]>dep[v]) swap(u,v);

    while(dep[u]<dep[v])

    {

        if(a[v])

        {

            ans--;

            a[v]=;

        }

        v=father[v];

    }

    while(u!=v)

    {

        if(a[v])

        {

            ans--;

            a[v]=;

        }

        v=father[v];

        if(a[u])

        {

            ans--;

            a[u]=;

        }

        u=father[u];

    }

}

int main()

{

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

    int icase=;

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

    {

        int a,b;

        init();

        rep(i,,m)

        {

            scanf("%d%d",&a,&b);

            addedge(a,b);

        }

        tarjan(,);

        int tmp,u;

        rep(i,,n)

        {

            tmp=par[i]^;

            u=edge[tmp].to;

            if(DFN[u]<low[i])

            {

                edge[tmp].vis=edge[tmp^].vis=;

            }

        }

        rep(i,,n)

        {

            if(!label[i])

            {

                Bcnt++;

                part(i);

            }

        }

        ans=Bcnt-;

        rep(i,,n)

        {

            if(!edge[par[i]].vis)

            {

                tmp=par[i]^;

                u=edge[tmp].to;

                graph[label[u]].push_back(label[i]);

                graph[label[i]].push_back(label[u]);

            }

        }

        lca_bfs();

        int v,q;

        scanf("%d",&q);

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

        rep(i,,q)

        {

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

            lca(label[u],label[v]);

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

        }

        printf("\n");

    }

    return ;

}