POJ 3694 Network（双连通分量）

浏览数：31 / 时间：2015年06月09日

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

题意： N个点，M条边，构成一个连通图，将图中加入特定的一些边，每加一条边就输出加入这条边后图中剩的桥的个数。

思路：双连通分量，用LCA

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdio.h>
#include <string.h>

using namespace std;

const int maxn = 100005 ;
const int maxm = 555555 ;
const int INF = 1000000000 ;

struct Edge
{
    int v, next;
}map[maxm];

int low[maxn],dfn[maxn],index,vis[maxn] ;
int e,n,m,a,b,head[maxn] ;
int cnt,bridge[maxn],father[maxn] ;

void Init()
{
    e = 0 ; index = 0 ; cnt = 0 ;
    memset(vis,0,sizeof(vis)) ;
    memset(bridge,0,sizeof(bridge)) ;
    memset(dfn,0,sizeof(dfn)) ;
    memset(head,-1,sizeof(head)) ;
    for(int i = 1 ; i <= n ; i++)
    father[i] = i ;
}

void addedge(int v,int w)
{
    map[e].v = w ;
    map[e].next = head[v] ;
    head[v] = e++ ;
}

void tarjan(int u)
{
    vis[u] = 1 ;
    dfn[u] = low[u] = ++index ;
    for(int i = head[u] ; i+1 ; i = map[i].next)
    {
        int v = map[i].v ;
        if(!vis[v])
        {
            father[v] = u ;
            tarjan(v) ;
            low[u] = min(low[u],low[v]) ;
            if(low[v] > dfn[u])
            {
                cnt++ ;
                bridge[v] = 1 ;
            }
        }
        else if(vis[v] == 1 && v != father[u])
        low[u] = min(low[u],dfn[v]) ;
    }
    vis[u] = 2 ;
}

void lca(int u,int v)
{
    while(dfn[u] > dfn[v])
    {
        if(bridge[u]) cnt--,bridge[u] = 0 ;
        u = father[u] ;
    }
    while(dfn[v] > dfn[u])
    {
        if(bridge[v]) cnt--,bridge[v] = 0 ;
        v = father[v] ;
    }
    while(u != v)
    {
        if(bridge[u]) cnt--,bridge[u] = 0 ;
        if(bridge[v]) cnt--,bridge[v] = 0 ;
        u = father[u] ;
        v = father[v] ;
    }
}
int main()
{

    int kase = 0 ;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        if(n == 0 && m == 0) break ;

        Init() ;
        while(m--)
        {
            scanf("%d %d",&a,&b) ;
            addedge(a,b) ;
            addedge(b,a) ;
        }
        tarjan(1) ;
        int k ;
        scanf("%d",&k) ;
        printf("Case %d:\n",++kase) ;
        while(k--)
        {
            scanf("%d %d",&a,&b) ;
            lca(a,b) ;
            printf("%d\n",cnt) ;
        }
        printf("\n") ;
    }
    return 0;
}