割点（割边）

W1nNy_ · 2021-07-05 11:02:30 · 个人记录

无向图的割点与割边

高ping学渣

给定无向图 G=(V,E)

对于 x \in V ,从图中删去节点x以及所有关联的边之后， G 分裂成两个不相连的子图，我们称 x 为 G 的割点。

对于 e \in E ,从图中删去边e之后， G 分裂称两个不相连的子图，称 e 为 G 的桥或割边。

追溯值

在dfs过程中，我们需要维护一个 low 数组，low[u] 表示在以 u 为根的子树中，子树中的节点以及通过一条非树边能到达以 u 为根的子树中的的节点

搜索过程中，应初始化 low[u]=dfn[u] ,搜索时用 low[v](v \in subtree(u)) 来更新 low[u]

如下图，红色线为非树边，

割点判定法则

如果 u 是搜索树的根节点，那么如果根节点有两个以上的子树的话， 它一定是割点，我们可以记录根节点 root 的子树个数，当 rootchild \ge 2 时，root 即为割点。 如果 u 不是根节点的话，当以 u 为根的搜索树上，存在一个节点 v 满足 dfn[u]\le low[v] 时，cut[u]=1,

模板：

P3388 割点模板

  #include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int N=2e4+10,M=1e5+10;
int head[N+N],net[M+M],edge[M+M],dfn[N],low[N];
int ts=1,idx;
bool cut[N];
void add(int x,int y)
{
    edge[idx]=y;
    net[idx]=head[x];
    head[x]=idx++;
}
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=ts++;//初始化
    int child=0;//子树数量
    for(int i=head[u];i!=-1;i=net[i])
    {
        int v=edge[i];
        if(!dfn[v])//v节点没有被访问过（v是以u为根的搜索树上的节点）
        {
            tarjan(v,fa);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u] && u!=fa) cut[u]=1;
            //注意判断条件
            if(u==fa)   child++;//记录子树数量
        }
        else low[u]=min(low[u],dfn[v]);
        // 边（u，v）不是搜索树上的边（v节点被访问了）
    }
    if(child>=2 && u==fa)   cut[fa]=1;
    //如果根节点子树数量>=2，则根节点为割点
    return ;
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,m;
    cin>>n>>m;
    for(int i=1,x,y;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    int ans=0;
    for(int i=1;i<=n;i++)   if(!dfn[i]) tarjan(i,i);
    for(int i=1;i<=n;i++)   if(cut[i])  ans++;
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)   if(cut[i])  printf("%d ",i);
    return 0;
}

应用：洛谷割点唯一一道蓝题[doge] & 蓝书例题

P3469 [POI2008]BLO-Blockade

分类讨论：

1.当点 u 不是割点时：访问次数减少了 2(n-1) 次

2.当点 u 是割点时： 访问次数减少的数量为删除了割点u之后所有连通块的大小 size[i] 与 n-size[i] 的乘积 与剩下所有点 rest 和当前割点 u 的访问数量的和