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了),再加边。

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

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

POJ 3694Network(Tarjan边双联通分量 + 缩点 + LCA并查集维护)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#include <map>
using namespace std;

const int maxn = 1e6 + 5;
const int maxm = maxn<<1;
struct edge{
    int to, next;
} ed[maxm<<1];
int n, m, q;
int head[maxn], tot;
int dfn[maxn], low[maxn], num, ans, c[maxn], dcc;
int hc[maxn], vc[maxm<<1], nc[maxm<<1], tc;
int pre[maxn], fa[maxn], dep[maxn], pass;
bool brige[maxn], vis[maxn];
inline void init(){
    memset( head, -1, sizeof(head) );
    memset( dfn, 0, sizeof(dfn) );
    memset( brige, 0, sizeof(brige) );
    memset( c, 0, sizeof(c) );
    memset( vis, 0, sizeof(vis) );
    tot = 1;
}

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!=-1; 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^1] = 1;          
                ans ++;
            }
        }else if( i!=(in_edge^1) ) 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!=-1; 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!=-1; i=nc[i] ){
        int y = vc[i];
        if( y!=fa[x] ){
            fa[y] = x;
            dep[y] = dep[x] + 1;
            dfs_lca(y);
        }
    }
}

inline void LCA( int x, int y ){
    pass = 0;
    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 += 2;
    }
}

int main(){
    // freopen("in.txt", "r", stdin);
    int kase = 1;
    while( ~scanf("%d%d", &n, &m), n||m ){
        init();
        for( int i=0; i<m; i++ ){
            int u, v;
            scanf("%d%d", &u, &v);
            add(u, v);
        }
        ans = dcc = num = 0;
        tarjan(1, 0);
        for( int i=1; i<=n; i++ ) if( !c[i] ) ++dcc, dfs_dcc(i);
        memset( hc, -1, sizeof(hc) );
        tc = 1;
        //不要使用map作为标记,遍历边进行新图的加边操作,map会TLE
        for( int u=1; u<=n; u++ ){
            for( int i=head[u]; i!=-1; i=ed[i].next ){
                int v = ed[i].to;
                if( c[u]==c[v] ) continue;
                add_dcc(c[u], c[v]);
            }
        }
        ans = tc>>1;
        dep[1] = 1;
        fa[1] = 0;
        dfs_lca(1);           
        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 0;
}
先求桥,再求边双联通,再连边进行LCA POJ 3694Network(Tarjan边双联通分量 + 缩点 + LCA并查集维护)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#include <map>
using namespace std;

const int maxn = 1e6 + 5;
const int maxm = maxn<<1;
struct edge{
    int to, next;
} ed[maxm<<1];
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<<1], nc[maxm<<1], tc;
int pre[maxn], fa[maxn], dep[maxn], pass;
bool ins[maxn], vis[maxn];
inline void init(){
    memset( head, -1, sizeof(head) );
    memset( dfn, 0, sizeof(dfn) );
    memset( c, 0, sizeof(c) );
    memset( vis, 0, sizeof(vis) );
    tot = 1;
}

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] = 1;
    st[++st[0]] = x;
    for( int i=head[x]; i!=-1; i=ed[i].next ){
        int y = ed[i].to;
        if( i==(in_edge^1) ) 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[0]--];
            c[p] = dcc;
            ins[p] = 0;
        }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!=-1; i=nc[i] ){
        int y = vc[i];
        if( y!=fa[x] ){
            fa[y] = x;
            dep[y] = dep[x] + 1;
            dfs_lca(y);
        }
    }
}

inline void LCA( int x, int y ){
    pass = 0;
    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 += 2;
    }
}

int main(){
    // freopen("in.txt", "r", stdin);
    int kase = 1;
    while( ~scanf("%d%d", &n, &m), n||m ){
        init();
        for( int i=0; i<m; i++ ){
            int u, v;
            scanf("%d%d", &u, &v);
            add(u, v);
        }
        ans = dcc = num = 0;
        for( int i=1; i<=n; i++ ) if(!dfn[i]) tarjan(1, 0);
        memset( hc, -1, sizeof(hc) );
        tc = 1;
        for( int u=1; 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>>1;
        dep[1] = 1;
        fa[1] = 0;
        dfs_lca(1);
        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 0;
}
求强联通分量,再加边,进行LCA

 

上一篇:【luogu3388】 【模板】割点(割顶)[tarjan 割点]


下一篇:[tarjan][树上差分] Codeforces 555E Case of Computer Network