hdu2460&&poj3694 缩点+lca变形

http://acm.hdu.edu.cn/showproblem.php?pid=2460

http://poj.org/problem?id=3694

3 2
1 2
2 3
2
1 2
1 3
4 4
1 2
2 1
2 3
1 4
2
1 2
3 4
0 0

Case 1:
1
0

Case 2:
2
0

/**
hdu2460&&poj3694   缩点+lca变形
题目大意：给定一个图，然后依次加一些边，求每加入一条边后现有的图中含有多少桥
解题思路：先把所有的强连通分量进行缩点，然后现有桥的个数为点数减一，而后每增加一条边u->v那么u，v到它们lca所在的环之间的桥都要减去。
           先dfs将所有的桥标记（采用标记点的方式标记桥），然后每次加边来一次向根节点查找就好了
*/
#pragma comment(linker, "/STACK:10240000000000,10240000000000")/// 申请空间hdu需要
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn=200005;

int head[maxn],ip;
int m,n,bridge,ans;
int low[maxn],dfn[maxn],dex,cnt,st[maxn],inst[maxn],belong[maxn],top;

void init()
{
    memset(head,-1,sizeof(head));
    ip=0;
}

struct note
{
    int v,cut,next;
}edge[maxn*2];

void addedge(int u,int v)
{
    edge[ip].v=v,edge[ip].cut=0,edge[ip].next=head[u],head[u]=ip++;
}

void tarjan(int u,int pre)
{
    dfn[u]=low[u]=++dex;
    st[top++]=u;
    inst[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==pre)continue;
        if(dfn[v]==0)
        {
            tarjan(v,u);
            if(low[u]>low[v])low[u]=low[v];
            if(low[v]>low[u])
            {
                bridge++;
                edge[i].cut=1;
                edge[i^1].cut=1;
            }
        }
        else if(inst[v]&&low[u]>dfn[v])
        {
            low[u]=dfn[v];
        }
    }
    if(dfn[u]==low[u])
    {
        int j;
        cnt++;
        do
        {
            j=st[--top];
            inst[j]=0;
            belong[j]=cnt;
        }
        while(j!=u);
    }
}
vector <int> vec[maxn];
int father[maxn];
int dep[maxn];
int a[maxn];

void bfs(int root)
{
    memset(dep,-1,sizeof(dep));
    dep[root]=0;
    a[root]=0;
    father[root]=-1;
    queue<int>q;
    q.push(root);
    while(!q.empty())
    {
        int tmp=q.front();
        q.pop();
        for(int i=0;i<vec[tmp].size();i++)
        {
            int v=vec[tmp][i];
            if(dep[v]!=-1)continue;
            dep[v]=dep[tmp]+1;
            a[v]=1;
            father[v]=tmp;
            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]=0;
        }
        v=father[v];
    }
    while(u!=v)
    {
        if(a[u])
        {
            ans--;
            a[u]=0;
        }
        if(a[v])
        {
            ans--;
            a[v]=0;
        }
        v=father[v];
        u=father[u];
    }
}

void solve()
{
    memset(dfn,0,sizeof(dfn));
    memset(inst,0,sizeof(inst));
    cnt=dex=top=bridge=0;
    tarjan(1,-1);
    for(int i=0;i<n;i++)
        vec[i].clear();
    for(int u=1;u<=n;u++)
    {
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            if(edge[i].cut)
            {
                int x=belong[u];
                int y=belong[v];
                vec[x].push_back(y);
                vec[y].push_back(x);
            }
        }
    }
    bfs(1);
    int Q;
    //printf("%d %d\n",cnt-1,bridge);
    ans=cnt-1;
    scanf("%d",&Q);
    while(Q--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        lca(belong[u],belong[v]);
        printf("%d\n",ans);
    }
    printf("\n");
}
int main()
{
    int T,tt=0;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0)break;
        init();
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        printf("Case %d:\n",++tt);
        solve();
    }
    return 0;
}

hdu2460&&poj3694 缩点+lca变形

原文：http://blog.csdn.net/lvshubao1314/article/details/44016771