【MIX】无向图的割点&桥&双连通分量

2853

2020.07.03

发布于未知归属地

前文链接: 强连通分量(2)
基本概念
基本算法
1. tarjan判断割点与桥
2. 求双连通分量
  1. 模板代码
例题
参考资料

前文链接: 强连通分量(2)

基本概念

点-连通度: 将图 $G$ 变成不连通图(平凡图)所需要删除的最少顶点数称为 $G$ 的连通度, 设为 $k (G)$ . 当图 $G$ 是平凡图时, $k (G) = 0$ ; 图 $G$ 为连通图且存在割点时, $k (G) = 1$ ; $G$ 是完全图时, $k (G) = n - 1$ .
边-连通度: 将图 $G$ 变成平凡图需要从 $G$ 中删除的最少边称为 $G$ 的边连通度, 记为 $λ (G)$ . 当 $G$ 是平凡图时, $λ (G) = 0$ , 当 $G$ 是完全图时, $λ (G) = n - 1$ .
点-双连通(v-BCC): 如果一个无向连通图的点连通度大于1, 则称该图是点-双连通的; 也是无向连通图中极大的, 不包含割点的连通块.
边-双连通(e-BCC): 如果一个无向连通图的边连通度大于1, 则称该图是边-双连通的; 也是无相连通图中极大的, 不包含桥的连通块.
双连通分量(BCC): 在图 $G$ 的所有子图 $G^{'}$ 中, 如果 $G^{'}$ 是双连通的, 则称 $G^{'}$ 为双连通子图, 如果 $G^{'}$ 不是任何一个双连通子图的真子集, 则 $G^{'}$ 是极大双连通子图也就是双连通分量.

点双连通分量又叫做块

边双连通分量一定是点双连通分量, 但是点双连通分量不一定是边双连通分量

基本算法

tarjan判断割点与桥

与tarjan scc算法类似, 定义在无向图DFS中会遇到的三类边(有向图DFS时会多一种横叉边)

树枝边: DFS时经过的边, 即DFS搜索树上的边
前向边: 与DFS方向一致, 从某个节点指向子孙的边
后向边: 与DFS方向相反, 从某个节点指向其祖先的边

dfn[u]表示u在搜素树中被遍历的的时间戳
low[u]表示u或者u的子树的节点经过最多一条后向边能追溯到的最早树中节点的时间戳
当 $(u, v)$ 为树枝边, $u$ 为 $v$ 为父节点, 则 $L o w (u) = min {L o w (u), L o w (v)}$ .
当 $(u, v)$ 为后向边, $v$ 不为 $u$ 的父节点, 则 $L o w (u) = min {L o w (u), D FN (v)}$

判断割点

一个顶点u是割点, 当且仅当满足以下两个条件之一:

u为树根, 且u有多于一个子树.

假设u只有一棵子树, 去掉根节点后肯定不会出现多棵子树, 因此不可能为割点; 而无向图DFS搜索树中不存在横叉边, 所以若有多个子树, 这些子树之间不会有边相连, 因此u肯定是割点. $□$

u不为树根, 且满足存在 $(u, v)$ 为树枝边, 且 $D FN (u) \leq L o w (v)$ , 因为删除u后, v的子树不能到达u的祖先, u成为了割点.

模板代码

c++

void tarjan(int u){
    dfn[x]=low[x]=++ts;
    int cnt=0;
    for(int i=head[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        if(!dfn[v]){ // 当前为树枝边
            ++cnt; // 子树数量计数
            tarjan(v);
            low[x]=min(low[u], low[v]);
            // 使用条件1 || 条件2判断
            if((u==root && cnt>1) || (u!=root && dfn[u]<=low[v])) cut[u]=1;
        }
    }
}

判断桥

一条无向边 $(u, v)$ 是桥, 当且仅当 $(u, v)$ 是树枝边, 且满足 $D FN (u) < L o w (v)$ , 考虑到重边问题, 需要将一条无向边拆分为两条编号一样的有向边, 用邻接表进行存储. 在判断 $(u, v)$ 是否为后向边时需要判断树枝边的反向边还是新的一条边.

模板代码

c++

void tarjan(){
    low[u]=dfn[u]=++ts;
    for(int e=adj[u], v; e; e=ne[e]){
        if(e==(front[u]^1)) continue; // 不考虑树枝边
        if(!dfn[v==go[e]]){
            from[v]=e;
            tarjan(v);
            if(low[v]<low[u]) low[u]=low[v];
            if(low[v]>dfn[u]) cut[from[v]]=cut[from[v]^1]=true; // 找到桥
        }
        else if(dfn[v]<low[u]) low[u]=dfn[v];
    }
}

求双连通分量

一个点可以属于多个BCC, 而一条边属于唯一的BCC, 每次遇到树枝边和后向边, 就将它们压入栈中, 当DFS从一个点 $u$ 返回点 $v$ 时, 如果 $l o w [u] \geq df n [n]$ , 就不断地将栈顶边出栈, 直到弹出边 $(u, v)$ 为止, 所有弹出的边构成了BCC.

割点可以属于多个vBCC, 其余点和每条边只属于一个vBCC, 对于两个vBCC, 最多只有一个公共点(割点).
桥不属于任何一个eBCC, 其余的边和每个顶点都属于且只属于一个eBCC, 可以使用并查集实现.

模板代码

c++

const int maxn=1005;
vector<int> edge[maxn];
vector<vector<int>> connect;
int dfn[maxn], low[maxn], in_seq[maxn];
int stack[maxn], list[maxn];
int cnt, top, pop, len;
void tarjan(int v){
    stack[++top]=v;
    dfn[v]=low[v]=pop++;
    int i, succ;
    for(int i=edge[v].size()-1; i>=0; --i){
        succ=edge[v][i];
        if(dfn[succ]==-1){
            tarjan(succ);
            if(low[succ]>=dfn[v]){
                ++cnt;
                len=0;
                do{
                    in_seq[stack[top]]=cnt;
                    list[len++]=stack[top];
                    --top;
                }while(stack[top+1]!=succ);
                in_seq[v]=cnt;
                list[len++]=v;
                vector<int> tmp(list, list+len);
                connect.push_back(tmp);
            }
            low[v]=min(low[v], low[succ]);
        }else low[v]=min(low[v], dfn[succ]);
    }
}

例题

POJ 3177/NewCoder 10774/ACW 395. 冗余路径

要求任意两条边有两条没有公共的边的路, 等价于该图是边双连通图

充分性: 图 $G$ 任意两点之间至少有两条没有公共边的路 $\to$ 图 $G$ 的最小割边集合中的边至少有2条 $\to$ 边连通度>=2 $\to$ 图 $G$ 是边双连通图.
必要性: 图 $G$ 是边双连通图 $\to$ 图 $G$ 的连通度>=2 $\to$ 图 $G$ 的最小割边集合中的边数至少为2 $\to$ 图 $G$ 中任意两点之间存在至少两条分离路径.

考虑将一个有桥的连通图, 通过加边变成BCC. 首先找到所有的桥, 然后删除桥边, 剩下的每个连通块都是双连通子图, 将每个双连通子图收缩为一个点, 再将桥边加回来, 最后这个图是一棵树, 边的连通度为1. 统计树中度为1的节点个数, 设为 $l e a f$ , 则至少在树上添加 $(l e a f + 1) /2$ 条边, 可以使树达到eBCC.

c++

#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;

const int N=5005;
const int M=20005;
int n, m;
int head[N], E=0;
int dfn[N], low[N], ts=0;
stack<int> st;
int id[N], ebcc_cnt=0; // 边双连通分量计数
bool is_bridge[N];
int d[N]; // 统计点的度数

struct Edge{int v, ne;}e[M];

inline void add(int a, int b){
    e[E].v=b;
    e[E].ne=head[a];
    head[a]=E++;
}

void tarjan(int u, int from){
    dfn[u]=low[u]=++ts;
    st.push(u);
    for(int i=head[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        if(!dfn[v]){ // 如果是树枝边
            tarjan(v, i);
            low[u]=min(low[u], low[v]);
            if(dfn[u]<low[v]){ // 连续的较小的偶数和较大的奇数构成桥, (0, 1), (2,3), (4,5)
                is_bridge[i]=is_bridge[i^1]=true; 
            }
        }
        else if(i!=(from^1)){ // 如果不是反向边更新low[u]
            low[u]=min(low[u], dfn[v]);
        }
    }
    
    if(dfn[u]==low[u]){ 
        ++ebcc_cnt;
        int j;
        do{
            j=st.top(); st.pop(); id[j]=ebcc_cnt;
        }while(j!=u);
    }
}

int main(){
    cin>>n>>m;
    memset(head, -1, sizeof head);
    while(m--){
        int a, b;
        // 建立无向图
        cin>>a>>b;
        add(a, b);
        add(b, a);
    }
    
    tarjan(1, -1);
    for(int i=0; i<E; ++i){
        if(is_bridge[i]) d[id[e[i].v]]++;
    }
    
    
    // 统计缩点后度数为1的点
    // 根据结论计算, 需要添加边的数量为(cnt+1)/2
    int cnt=0;
    for(int i=1; i<=ebcc_cnt; ++i)
        if(d[i]==1) ++cnt;
    
    cout<<(cnt+1)/2<<endl;
    
    return 0;
}

POJ 2117/NewCoder 50405/ACW 1183. 电力

本题要求求出无向连通图中的割点.
设当前搜索路径为 $u \to v$ , 满足关系 $l o w [v] >= df n [u]$ , 割点 $u$ 判断分两种情况:

$u$ 不是根节点, 那么 $u$ 是割点.
$u$ 是根节点, 那么 $u$ 至少有2个子节点(子树).

枚举每个连通块的root节点, 设移除该点后, 得到最多连通块的数量为ans, 原图中连通块的数量为cnt, 可以得到最多连通块数量为ans+cnt-1.
套用tarjan求割点的算法模板求解

c++

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>

using namespace std;

const int N=10005;
const int M=30005;

int n, m;
int head[N], E=0; // graph
int dfn[N], low[N], ts=0; // tarjan
int root, ans=0;

struct Edge{
    int v, ne;
}e[M];

inline void add(int a, int b){
    e[E].v=b;
    e[E].ne=head[a];
    head[a]=E++;
} 

void tarjan(int u){
    dfn[u]=low[u]=++ts;
    int cnt=0; // 统计u节点的子树数量
    for(int i=head[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u], low[v]);
            if(low[v]>=dfn[u]) ++cnt; // v是u的子树节点
        }
        else low[u]=min(low[u], dfn[v]); // v不是u的子树节点, 更新low[u]
    }
    if(u!=root) ++cnt; // u不是根节点, 去掉u后形成的子树计算父节点所在的子树
    ans=max(ans, cnt);
}

int main(){
    while(scanf("%d%d", &n, &m), n||m){
        memset(dfn, 0x00, sizeof dfn);
        memset(low, 0x00, sizeof low);
        memset(head, -1, sizeof head);
        E=ts=0;
        while(m--){
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b);
            add(b, a);
        }
        ans=0; // 删除点后连通块最多可以分成几部分
        int cnt=0; // 统计连通块的个数
        // 枚举图中的根节点
        for(root=0; root<n; ++root){
            if(!dfn[root]){
                ++cnt;
                tarjan(root);
            }
        }
        printf("%d\n", ans+cnt-1);
    }
    
    return 0;
}

洛谷 3225/NewCoder 20099/ACW 396. 矿场搭建

假设图原本为点连通图(图中无割点), 图中任意两点均可以作为出口; 如果图中存在割点, 如果连通块x仅仅和割点相连接, 该连通块中至少要放置一个救援点; 如果和多个割点相连的块则没有必要建立逃生通道.
分为如下三种情况考虑

图中只有一个BCC, 不存在割点, 有 $C_{n}^{2}$ 种选点方案
一个BCC只有一个割点, 在非割点处任意选择一个点
割点数大于等于2, 不需要选点

c++

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;
const int N=1005;
const int M=1005;

int n, m;
int head[N], E=0; // graph
int dfn[N], low[N], ts=0; // tarjan
stack<int> st;
bool vis[N];
int ebcc_cnt;
vector<int> ebcc[N]; // 存储每个双连通分量中有哪些点
bool cut[N]; // 判断该点是否为割点
int root; // 特判root节点

struct Edge{int v, ne;}e[M];
inline void add(int a, int b){
    e[E].v=b;
    e[E].ne=head[a];
    head[a]=E++;
}

void tarjan(int u){
    dfn[u]=low[u]=++ts;
    st.push(u);
    
    if(u==root && head[u]==-1){
        ebcc_cnt++;
        ebcc[ebcc_cnt].push_back(u);
        return;
    }
    
    int cnt=0; // 子树的数量
    for(int i=head[u]; ~i; i=e[i].ne){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u], low[v]);
            if(dfn[u]<=low[v]){ // 割点判断条件
                ++cnt;
                if(u!=root || cnt>1) cut[u]=true;
                ++ebcc_cnt;
                int j;
                do{
                    j=st.top(); st.pop();
                    ebcc[ebcc_cnt].push_back(j);
                }while(j!=v);
                ebcc[ebcc_cnt].push_back(u);
            }
        }
        else low[u]=min(low[u], dfn[v]);
    }
}

int main(){
    int kase=1;
    while(cin>>m, m){
        for(int i=1; i<=ebcc_cnt; ++i) ebcc[i].clear();
        E=n=ts=ebcc_cnt=0;
        memset(head, -1, sizeof head);
        memset(dfn, 0x00, sizeof dfn);
        memset(cut, 0x00, sizeof cut);
        
        while(m--){
            int a, b;
            cin>>a>>b;
            n=max(n, a), n=max(n, b); // 得到所有点的数量
            add(a, b);
            add(b, a);
        }
        
        for(root=1; root<=n; ++root){
            if(!dfn[root]) tarjan(root);
        }
        int res=0; // 需要放置的救援点的数量
        ULL ans=1; // 放置救援点的方案数
        
        // 分类讨论
        for(int i=1; i<=ebcc_cnt; ++i){
            int cnt=0;
            // 统计割点的数量
            for(int j=0; j<ebcc[i].size(); ++j)
                if(cut[ebcc[i][j]]) ++cnt;
            
            // 一个BCC
            if(!cnt){
                if(ebcc[i].size()>1){
                    res+=2;
                    ans*=ebcc[i].size()*(ebcc[i].size()-1)/2;
                }
                else ++res;
            }
            // BCC有一个割点, 需要在BCC内部放一个救援点
            else if(cnt==1){
                ++res;
                ans*=ebcc[i].size()-1;
            }
        }
        cout<<"Case "<<kase++<<": "<<res<<" "<<ans<<endl;
    }
    
    return 0;
}

参考资料

算法设计编程实验 吴永辉王建德 机械工业出版社
算法竞赛入门经典 刘汝佳陈锋 清华大学出版社
信息学奥赛一本通 曹文等 福建教育出版社
ACW平台