连通性问题（2）- 割点和桥

概念

割点、桥是在无向图中的概念。

割点：删除节点 $u$ 后，原图变为不连通，则称 $u$ 为割点。
桥（割边）：删除边 $(u,v)$ 后，原图变为不连通，则称 $(u,v)$ 为桥。
点双连通：不存在割点的无向图称为点双连通图。
边双连通：不存在桥的无向图称为边双连通图。

一张点双连通图不一定是边双连通图，割点之间的连边不一定是桥，桥的起点和终点也不一定是割点。

割点

我们来考虑如何修改 Tarjan 算法求割点。

如上图，对于节点 $u$ 来说，若存在 $u$ 的子节点 $v$ ，使得 $\text{low}_v\geq\text{dfn}_u$ ，则 $u$ 为割点。（因为从节点 $v$ ，无法回到 $u$ 的父节点，则删除 $u$ 后， $v$ 与图其余部分不连通）

但对于根节点来说，这个判断是错误的。考虑只有一个子树的根节点。此时删除根结点后，原图仍然连通（本质即上文中图其余部分不存在了）。因此，对于根节点，我们需要判断子树数量。若子树数量多于一个，则根节点为割点，反之则不是。

桥

首先，桥一定是树枝边。（因为仅有树枝边的搜索树就是连通的，删除任何非树枝边后，原图一定还连通）

对于树枝边 $(u,v)$ ，其中 $u$ 是 $v$ 的祖先，若有 $\text{low}_v>\text{dfn}_u$ ，则边 $(u,v)$ 为桥。注意这里条件和割点的差异。因为如果有 $\text{low}_v=\text{dfn}_u$ ， $v$ 也能连回 $u$ ，原图仍连通。

实现

对 Tarjan 算法略加修改即可。注意到我们删除了栈，因为在求割点和桥时不需要，所以也无需判断搜索节点是否在栈中。

变量 cnt 计算子树个数，且若 u==fa，则此时 u 为根节点。调用时采用 tarjan(root,root);。

void tarjan(int u,int fa){
    dfn[u]=low[u]=++dfs_cnt;
    int cnt = 0;
    for(auto v:G[u]){
        if(!dfn[v]){
            cnt++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if((low[v]>=dfn[u] && u!=fa) || (u==fa && cnt>1)){
                // 是割点
                printf("%d is cut vertex.\n",u);
            }
            if(low[v]>dfn[u]){
                // 是桥
                printf("(%d,%d) is a bridge.\n",u,v);
            }
        }
        else if(v!=fa){ // 不能从搜索树回到父节点
            low[u]=min(low[u],dfn[v]);
        }
    }
}

应用

拦截匪徒

题目描述

某市的地图是由 $n$ 个点组成的无向图，每个点代表一个区。现在 $p$ 区发生了抢劫案，而警察为了截住劫匪须埋伏在一个劫匪必经的区域。由于不知道劫匪会向那个区域逃窜，所以希望你计算出对于任意一个劫匪可能逃向的区域 $j$ ，找出一个可以拦截劫匪的区 $k(k \neq p, k \neq j)$ ，即劫匪从 $p$ 区逃向 $j$ 区，必经过 $k$ 区。由于地区 $j$ 可能是匪徒的老巢所在，所以警察希望能在路上拦住劫匪，而不是在 $j$ 区抓捕。（ $1 \leq p \leq n \leq 200$ ）

输入格式

第一行为 $n,p$ ，接下来为 $n \times n$ 的矩阵 $A$ ， $A[i,j]=1$ 表示i区与j区有路连接， $A[i,j]=0$ 则反之。

输出格式

输出 $n-1$ 行，按顺序从 $j=1,2,…,p-1,p+1,…,n$ 依次输出对于每一个 $j$ ，警察可以在那些点埋伏。如有多个点，要按从小到大的顺序依次输出，如没有，则对应输出“No”。

样例

输入样例：

输出样例：

No
No
2
2  4

枚举在每个点 $k$ 埋伏，然后用并查集维护节点连通性。若此时节点 $u$ 和 $p$ 不连通，则 $u$ 的答案包含 $k$ 。注意若 $u$ 和 $p$ 在原图上就不连通，答案应为 No （注意大小写）。
时间复杂度 $O(n^3)$ （因为采用了邻接矩阵）。

事实上，可以跑一遍 Tarjan 算法，能埋伏的点一定是割点，可以略微加快常数。

AC 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 205;

int G[N][N];

int n,p;
int dfn[N],low[N],dfs_cnt=0;
bool cut[N];

void tarjan(int u,int fa){
    dfn[u]=low[u]=++dfs_cnt;
    int cnt = 0;
    for(int v=1;v<=n;v++){
        if(!G[u][v])continue;
        if(!dfn[v]){
            cnt++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if((low[v]>=dfn[u] && u!=fa) || (u==fa && cnt>1)){
                cut[u]=1;
            }
        }

        else if(v!=fa){
            low[u]=min(low[u],dfn[v]);
        }
    }

}

int fa[N];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int i,int j){
    fa[find(i)]=find(j);
}
vector<int> ans[N];
bool can_reach[N];

int main(){
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&G[i][j]);
            if(G[i][j])merge(i,j);
        }
    }

    for(int i=1;i<=n;i++){
        can_reach[i]=find(i)==find(p);
    }

    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i,i); // 求割点
    }

    for(int i=1;i<=n;i++){
        if(!cut[i] || i==p || !can_reach[i])continue;


        for(int j=1;j<=n;j++){
            fa[j]=j;
        }

        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                if(k==i)continue;
                if(j==i)continue;
                if(G[j][k])merge(j,k);
            }
        }

        for(int j=1;j<=n;j++){
            if(j==i)continue;
            if(find(j) != find(p)){
                ans[j].push_back(i);
            }
        }


    }

    for(int i=1;i<=n;i++){
        if(i==p)continue;
        if(ans[i].size()==0 || !can_reach[i]){ // 如果 j 本来就到不了，输出 No
            puts("No");
        }else{
            for(int x:ans[i]){
                printf("%d ",x);
            }
            puts("");
        }
    }
    return 0;
}