POJ3694 Network【连通分量+LCA】

题意：

一个无向图可以有重边，下面q个操作，每次在两个点间连接一条有向边，每次连接后整个无向图还剩下多少桥（注意是要考虑之前连了的边，每次回答是在上一次的基础之上）。

思路：

首先运行一次Tarjan，求出桥和缩点，那么远无向图将缩点为一棵树，树边正好是原来的桥。每次连接两点，看看这两点是不是在同一个缩点内，如果是，那么缩点后的树没任何变化，如果两点属于不同的缩点，那么连接起来，然后找这两个缩点的LCA，因为从点u到LCA再到点v再到点u，将形成环，里面的树边都会变成不是桥。计数的时候注意，有些树边可能之前已经被标记了，这次再经过不能再标记。

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

#define N 100010

#define M 200010

vector<int> ver[N];

int head[N],dfn[N],low[N],vis[N],fa[N],dcnt,bcnt;

struct edge{

    int u,v,used,next;

}e[*M];

bool isbridge[N];

inline void add(int u, int v ,int &k)

{

    e[k].v = v; e[k].used = ;

    e[k].next = head[u]; head[u] = k++;

}

void LCA(int u,int v)

{

    if(dfn[u] < dfn[v]) swap(u,v);

    while(dfn[u] > dfn[v])

    {

        if(isbridge[u]) bcnt--;

        isbridge[u] = false;

        u = fa[u];

    }

    while(u!=v)

    {

        if(isbridge[u]) bcnt--;

        if(isbridge[v]) bcnt--;

        isbridge[u] = isbridge[v] = false;

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

    }

}

void dfs(int u)

{

    vis[u] = ; dfn[u] = low[u] = ++dcnt;

    for(int k=head[u]; k!=-; k=e[k].next)

        if(!e[k].used)

        {

            e[k].used = e[k^].used = ;

            int v = e[k].v;

            if(!vis[v])

            {

                fa[v] = u;

                dfs(v);

                low[u] = min(low[u] , low[v]);

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

                { bcnt++; isbridge[v] = true; }

            }

            else if(vis[v] == ) low[u] = min(low[u],dfn[v]);

        }

    vis[u] = ;

}

int main()

{

    int n,m,q,cas=;

    while(cin>>n>>m,n,m)

    {

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

        int k = ;

        for(int i=; i<m; i++)

        {

            int u,v;

            cin>>u>>v;

            add(u,v,k);

            add(v,u,k);

        }

        memset(isbridge,false,sizeof(isbridge));

        memset(vis,,sizeof(vis));

        dcnt = bcnt = ;

        fa[] = ;

        dfs();

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

        cin>>q;

        while(q--)

        {

            int u,v;

            cin>>u>>v;

            LCA(u,v);

            cout<<bcnt<<endl;

        }

        cout<<endl;

    }

    return ;

}

巴特西

POJ3694 Network【连通分量+LCA】

最新文章

热门文章