POJ 3694Network(Tarjan边双联通分量 + 缩点 + LCA并查集维护)

【题意】：

有N个结点M条边的图，有Q次操作，每次操作在点x, y之间加一条边，加完E(x, y)后还有几个桥（割边），每次操作会累积，影响下一次操作。

【思路】：

先用Tarjan求出一开始总的桥的数量，然后求边双联通分量并记录每个结点v所属的连通分量号c[v]，之后进行缩点，将每个双联通分量作为都缩成一个新点，如果新点之间可以连边就连边

(能不能连边取决于原图，我就不多bb辽，XD)，形成新图。

对于每次询问x, y，判断c[x]!=c[y]，然后从c[x]和c[y]分别向上寻找父结点，找到LCA，对c[x]寻找时经过的边数+对c[y]寻找时经过的边数==应该减去的桥数。

考虑到每次操作的累加性，已经在之前操作中经过的边已经不是桥，不能在后续操作中再进行统计，所以使用并查集，每当c[x]，c[y]找到lca时，就将pre[c[x]] = pre[c[y]] = lca。

求LCA时涉及几乎涉及到每条边，就不使用倍增LCA（主要是我不会？？），而是用定义的方法。

下面上代码，第一个代码是求了桥，然后再进行求强联通分量，再加边。第二个是先求强联通分量(当然是有限制的，不然因为整个图就是联通的，肯定就一个SCC了)，再加边。

个人倾向于第二种袄，而且速度快

#include <iostream>

#include <cstring>

#include <cstdio>

#include <map>

#include <map>

using namespace std;

const int maxn = 1e6 + ;

const int maxm = maxn<<;

struct edge{

    int to, next;

} ed[maxm<<];

int n, m, q;

int head[maxn], tot;

int dfn[maxn], low[maxn], num, ans, c[maxn], dcc;

int hc[maxn], vc[maxm<<], nc[maxm<<], tc;

int pre[maxn], fa[maxn], dep[maxn], pass;

bool brige[maxn], vis[maxn];

inline void init(){

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

    memset( dfn, , sizeof(dfn) );

    memset( brige, , sizeof(brige) );

    memset( c, , sizeof(c) );

    memset( vis, , sizeof(vis) );

    tot = ;

}

inline void add( int u, int v ){

    ed[++tot].to = v; ed[tot].next = head[u]; head[u] = tot;

    ed[++tot].to = u; ed[tot].next = head[v]; head[v] = tot;

}

inline int min( int a, int b ){

    return a<b ? a:b;

}

inline void tarjan( int x, int in_edge ){

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

    for( int i=head[x]; i!=-; i=ed[i].next ){

        int y = ed[i].to;

        if(!dfn[y]){

            tarjan(y, i);

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

            if( dfn[x]<low[y] ){

                brige[i] = brige[i^] = ;

                ans ++;

            }

        }else if( i!=(in_edge^) ) low[x] = min(low[x], dfn[y]);

    }

}

inline void add_dcc( int u, int v ){

    vc[++tc] = v;

    nc[tc] = hc[u];

    hc[u] = tc;

}

inline void dfs_dcc( int x ){

    c[x] = dcc;

    for( int i=head[x]; i!=-; i=ed[i].next ){

        int y = ed[i].to;

        if( brige[i] || c[y] ) continue;

        dfs_dcc(y);

    }

}

inline int find( int x ){

    return pre[x]==x ? x:pre[x] = find(pre[x]);

}

inline void dfs_lca( int x ){               //结点分层

    pre[x] = x;

    for( int i=hc[x]; i!=-; i=nc[i] ){

        int y = vc[i];

        if( y!=fa[x] ){

            fa[y] = x;

            dep[y] = dep[x] + ;

            dfs_lca(y);

        }

    }

}

inline void LCA( int x, int y ){

    pass = ;

    x = find(x); y = find(y);           //直接将x,y向上寻找的路径中已经计算过得边略过

    while( dep[y]!=dep[x] ){

        if( dep[y]>dep[x] ){

            int f = find(fa[y]);             //当pre[y] == y时f是y的父亲，当pre[y]在y上方时，f就是相当于爷爷或者更高的祖辈

            y = pre[y] = f;             //不能写成pre[y] = y = f这样y先被赋值，pre[y]则改变的是赋值后的y即pre[f]被改变

            pass ++;

        }else{

            int f = find(fa[x]);

            x = pre[x] = f;

            pass++;

        }

    }

    while( find(x)!=find(y) ){

        pre[x] = find(fa[x]);

        pre[y] = find(fa[y]);

        x = pre[x]; y = pre[y];

        pass += ;

    }

}

int main(){

    // freopen("in.txt", "r", stdin);

    int kase = ;

    while( ~scanf("%d%d", &n, &m), n||m ){

        init();

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

            int u, v;

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

            add(u, v);

        }

        ans = dcc = num = ;

        tarjan(, );

        for( int i=; i<=n; i++ ) if( !c[i] ) ++dcc, dfs_dcc(i);

        memset( hc, -, sizeof(hc) );

        tc = ;

        //不要使用map作为标记，遍历边进行新图的加边操作，map会TLE

        for( int u=; u<=n; u++ ){

            for( int i=head[u]; i!=-; i=ed[i].next ){

                int v = ed[i].to;

                if( c[u]==c[v] ) continue;

                add_dcc(c[u], c[v]);

            }

        }

        ans = tc>>;

        dep[] = ;

        fa[] = ;

        dfs_lca();

        scanf("%d", &q);

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

        while( q-- ){

            int x, y;

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

            if( c[x]!=c[y] ){

                LCA(c[x], c[y]);

                ans -= pass;

            }

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

        }

        puts("");

    }

    return ;

}

先求桥，再求边双联通，再连边进行LCA

#include <iostream>

#include <cstring>

#include <cstdio>

#include <map>

#include <map>

using namespace std;

const int maxn = 1e6 + ;

const int maxm = maxn<<;

struct edge{

    int to, next;

} ed[maxm<<];

int n, m, q;

int head[maxn], tot, st[maxn];

int dfn[maxn], low[maxn], num, ans, c[maxn], dcc;

int hc[maxn], vc[maxm<<], nc[maxm<<], tc;

int pre[maxn], fa[maxn], dep[maxn], pass;

bool ins[maxn], vis[maxn];

inline void init(){

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

    memset( dfn, , sizeof(dfn) );

    memset( c, , sizeof(c) );

    memset( vis, , sizeof(vis) );

    tot = ;

}

inline void add( int u, int v ){

    ed[++tot].to = v; ed[tot].next = head[u]; head[u] = tot;

    ed[++tot].to = u; ed[tot].next = head[v]; head[v] = tot;

}

inline int min( int a, int b ){

    return a<b ? a:b;

}

inline void tarjan( int x, int in_edge ){

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

    ins[x] = ;

    st[++st[]] = x;

    for( int i=head[x]; i!=-; i=ed[i].next ){

        int y = ed[i].to;

        if( i==(in_edge^) ) continue;

        if(!dfn[y]){

            tarjan(y, i);

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

        }else if( ins[y] ) low[x] = min(low[x], dfn[y]);

    }

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

        dcc ++;

        int p;

        do{

            p = st[st[]--];

            c[p] = dcc;

            ins[p] = ;

        }while( p!=x );

    }

}

inline void add_dcc( int u, int v ){

    vc[++tc] = v;

    nc[tc] = hc[u];

    hc[u] = tc;

}

inline int find( int x ){

    return pre[x]==x ? x:pre[x] = find(pre[x]);

}

inline void dfs_lca( int x ){

    pre[x] = x;

    for( int i=hc[x]; i!=-; i=nc[i] ){

        int y = vc[i];

        if( y!=fa[x] ){

            fa[y] = x;

            dep[y] = dep[x] + ;

            dfs_lca(y);

        }

    }

}

inline void LCA( int x, int y ){

    pass = ;

    x = find(x); y = find(y);

    while( dep[y]!=dep[x] ){

        if( dep[y]>dep[x] ){

            int f = find(fa[y]);             //当pre[y] == y时f是y的父亲，当pre[y]在y上方时，f就是相当于爷爷或者更高的祖辈

            y = pre[y] = f;             //不能写成pre[y] = y = f这样y先被赋值，pre[y]则改变的是赋值后的y即pre[f]被改变

            pass ++;

        }else{

            int f = find(fa[x]);

            x = pre[x] = f;

            pass++;

        }

    }

    while( find(x)!=find(y) ){

        pre[x] = find(fa[x]);

        pre[y] = find(fa[y]);

        x = pre[x]; y = pre[y];

        pass += ;

    }

}

int main(){

    // freopen("in.txt", "r", stdin);

    int kase = ;

    while( ~scanf("%d%d", &n, &m), n||m ){

        init();

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

            int u, v;

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

            add(u, v);

        }

        ans = dcc = num = ;

        for( int i=; i<=n; i++ ) if(!dfn[i]) tarjan(, );

        memset( hc, -, sizeof(hc) );

        tc = ;

        for( int u=; u<=n; u++ ){

            for( int i=head[u]; ~i; i=ed[i].next ){

                int v = ed[i].to;

                if( c[u]==c[v] ) continue;

                add_dcc(c[u], c[v]);

            }

        }

        ans = tc>>;

        dep[] = ;

        fa[] = ;

        dfs_lca();

        scanf("%d", &q);

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

        while( q-- ){

            int x, y;

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

            if( c[x]!=c[y] ){

                LCA(c[x], c[y]);

                ans -= pass;

            }

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

        }

        puts("");

    }

     return ;

}

求强联通分量，再加边，进行LCA

巴特西

POJ 3694Network(Tarjan边双联通分量 + 缩点 + LCA并查集维护)

最新文章

热门文章