poj 3694 Network 边双连通+LCA

题意：n个点，m条边，给你一个连通图，然后有Q次操作，每次加入一条边（A,B），加入边后，问当前还有多少桥，输出桥的个数。

解题思路：先将原连通图边双连通缩点成一颗树，Q次操作过程中对树进行LCA操作。具体看代码：

看网上也有不缩点的方法。

思路参考于：http://www.cnblogs.com/kuangbin/p/3184884.html

#include "stdio.h"   //poj 3177 边双连通问题 + LCA(最近公共祖先)

#include "string.h"

#include "vector"

#include "queue"

using namespace std;

#define N 100100

#define M 400200

struct node

{

    int x,y;

    bool visit;

    int next;

} edge[2*M];

int idx,head[N];

void Init()

{

    idx = 0;

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

}

void Add(int x,int y)

{

    edge[idx].x = x;

    edge[idx].y = y;

    edge[idx].visit = false;

    edge[idx].next = head[x];

    head[x] = idx++;

}

int time;

int low[N],dfn[N];

inline int MIN(int a,int b)

{

    return a<b?a:b;

}

int st[M],num;  //记录哪些点为桥

int stackk[2*M],top;  //模拟栈(本题栈中存的是点，不是边)

int n,m;

int countt; //记录有多少个双连通分量

int belong[N];

void lian_tong(int x)

{

    int t;

    countt++;

    while(1)

    {

        t = stackk[top];

        top--;

        belong[t] = countt;

        if(t==x) break;

    }

}

void DFS(int x)

{

    int i,y;

    stackk[++top] = x;

    low[x] = dfn[x] = ++time;

    for(i=head[x]; i!=-1; i=edge[i].next)

    {

        y = edge[i].y;

        if(edge[i].visit) continue;

        edge[i].visit = edge[i^1].visit = true;

        if(!dfn[y])

        {

            DFS(y);

            low[x] = MIN(low[x],low[y]);

            if(low[y]>dfn[x])

                st[num++] = i;  //记录桥（两边双连通分量必定由桥相连）

        }

        else

            low[x] = MIN(low[x],dfn[y]);

    }

    if(dfn[x]==low[x])

        lian_tong(x); //标记当前边双连通分量

}

int ans;

bool mark[N];

int deep[N];

int father[N];

vector<int> vec[N];  //存树

void LCA_bfs(int root)

{

    int i,x,y;

    memset(deep,-1,sizeof(deep));

    deep[root] = 0;

    mark[root] = false;

    father[root] = -1;

    queue<int> q;

    q.push(root);

    while(!q.empty())

    {

        x = q.front();

        q.pop();

        for(i=0; i<(int)vec[x].size(); ++i)

        {

            y = vec[x][i];

            if(deep[y]!=-1) continue;

            deep[y] = deep[x]+1;

            mark[y] = true;

            father[y] = x;

            q.push(y);

        }

    }

}

void swap(int &x,int &y)

{

    int t = x;

    x = y;

    y = t;

}

void LCA(int x,int y)

{

    if(deep[x] > deep[y]) swap(x,y);

    while(deep[x]<deep[y])

    {

        if(mark[y])

        {

            ans--;

            mark[y] = false;

        }

        y = father[y];

    }

    while(x!=y)

    {

        if(mark[x])

        {

            ans--;

            mark[x] = false;

        }

        if(mark[y])

        {

            ans--;

            mark[y] = false;

        }

        x = father[x];

        y = father[y];

    }

}

void Solve()

{

    int i;

    int x,y;

    countt = 0;  //统计边双连通分量的个数

    num = 0;  //统计桥的条数

    top = 0; //栈

    time = 0;

    memset(dfn,0,sizeof(dfn));

    DFS(1);

    for(i=1; i<=countt; ++i) vec[i].clear();

    for(i=0; i<num; ++i)  //遍历桥

    {

        x = edge[st[i]].x;

        y = edge[st[i]].y;

        x = belong[x];

        y = belong[y];

        vec[x].push_back(y);

        vec[y].push_back(x);

    }

    LCA_bfs(1);

    ans = countt - 1;

    int Q;

    int u,v;

    scanf("%d",&Q);

    while(Q--)

    {

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

        LCA(belong[u],belong[v]);

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

    }

    printf("\n");

}

int main()

{

    int i;

    int Case=0;

    int x,y;

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

    {

        Init();

        Case++;

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

        {

            scanf("%d %d",&x,&y);

            Add(x,y);

            Add(y,x);

        }

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

        Solve();

    }

    return 0;

}

巴特西

poj 3694 Network 边双连通+LCA

最新文章

热门文章