问题描述:

给定一张含有n个节点m条边的无向图。然后执行q次操作,每次向图中添加一条边,并询问无向图中“桥”的数量。

输入:

有多组数据,每组数据以n (n<=100000) m (m<=200000)开始
然后m行,每行两个数a, b表示ab之间存在一条无向边
然后一个整数q,表示q次操作
接下来q行,每行两个数a, b表示在ab之间加一条无向边
输入以两个0结束

输出:

对于每组数据每个操作,输出操作之后无向图中桥的数量。

思路:

题目也很明确的说到了是要求桥的数量,所以算法一定和边双联通分量有关。

首先是缩点,然后剩下来一棵树,我们可以发现这棵树上的每一条边都属于原无向图中的桥。然后考虑加边操作,每一次操作都使得a, b(边的两个端点)树上路径的边不再是桥了,所以我们就可以将答案减去这些不再是桥的边。

然后考虑如何实现。求树上两点路径依然使用lca,只是这次的lca不是基于倍增,而是基于并查集。我们可以将那些不再是桥的边用并查集将它们压缩,使得下次计算答案时不会访问它们,同时也保证了时间复杂度。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAXN 200005
using namespace std;

int n, m, q, t, ans, cnt, head[MAXN], a[MAXN], b[MAXN], f[MAXN];
int id, tot, top, low[MAXN], dfn[MAXN], c[MAXN], dep[MAXN], fa[MAXN], sta[MAXN];
bool bridge[MAXN*2], tag[MAXN*2], vis[MAXN];

struct Edge {int next, to, dis;} edge[MAXN*2];

void init()
{
    cnt=1; ans=id=tot=top=0;
    for(int i=0; i<=MAXN-5; i++) head[i]=low[i]=dfn[i]=dep[i]=c[i]=vis[i]=0;
    for(int i=1; i<=MAXN; i++) f[i]=i;
    for(int i=0; i<=MAXN*2-5; i++) bridge[i]=tag[i]=0;
}

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void tarjan(int x, int in)
{
    low[x]=dfn[x]=++id;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!dfn[to])
        {
            tarjan(to, i);
            low[x]=min(low[x], low[to]);
            if(low[to]>dfn[x]) bridge[i]=bridge[i^1]=1;
        }
        else if(i!=(in^1)) low[x]=min(low[x], dfn[to]);
    }
}

void dfs1(int x, int tot)
{
    c[x]=tot; vis[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(bridge[i] || vis[to]) continue;
        dfs1(to, tot);
    }
}

void dfs2(int x, int father)
{
    fa[x]=father;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==father) continue;
        dep[to]=dep[x]+1; ans++;
        dfs2(to, x);
    }
}

int find(int x)
{
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}

void lca(int x, int y)
{
    x=find(x); y=find(y);
    while(x!=y)
    {
        if(dep[x]>dep[y]) sta[++top]=x, x=find(fa[x]);
        else sta[++top]=y, y=find(fa[y]);
        ans--;
    }
    while(top) f[sta[top--]]=x;
}

int main()
{
    while(scanf("%d%d", &n, &m) && n && m)
    {
        init();
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d", &a[i], &b[i]);
            addedge(a[i], b[i]);
            addedge(b[i], a[i]);
        }
        tarjan(1, 0);
        for(int i=1; i<=n; i++) if(!vis[i]) dfs1(i, ++tot);

        cnt=1;
        for(int i=1; i<=MAXN-5; i++) head[i]=0;
        for(int i=1; i<=m; i++)
        {
            if(c[a[i]]==c[b[i]]) continue;
            addedge(c[a[i]], c[b[i]]);
            addedge(c[b[i]], c[a[i]]);
        }
        dfs2(1, 0);

        printf("Case %d:\n", ++t);
        scanf("%d", &q);
        for(int i=1; i<=q; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            lca(c[x], c[y]);
            printf("%d\n", ans);
        }
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注