『算法-ACM 竞赛-图论』无向图求割点（找桥）tarjan

无向图求割点（找桥）tarjan

本博客参考了李煜东的《算法竞赛进阶指南》，大家要是觉得这篇文章写的不错请大家支持正版。豆瓣图书

我在之前的博客中讲解了搜索序时间戳，这次我们讲讲追溯值的概念。

追溯值：

设 subtree（x）表示搜索树中，以 X 为根的子树。low[x]定义为一下节点的时间戳最小值：

1.subtree（x）中的节点。

2.通过 1 条不在搜素树上的边，能够到达 subtree（x）的节点。

以上图为例。为了叙述简便，我们用时间戳代替节点编号。subtree（2）={2，3，4，5}。零位，节点 1 通过搜索树边的（1，5)能够到达 subtree（2）。所以 low[2]=1。根据定义拉算的话，首先应该让 low[x]=dfn[x]，然后考虑从 x 出发的每条边（x，y）;

若在搜素树上 x 是 y 的父节点，则令 low[x]=min（low[x],low[y]).

若无向边（x，y）不是搜索树边，则令 low[x]=min（low[x]，dfn[y]).

该图中写出了追溯值的图。

割点判定法则：

若 X 不是 Y 的搜素树的根节点（深度遍历的起点），则 x 是割点当且仅当搜索树上存在 X 的一个子节点 Y，满足：

dfn[x]<=low[y]

特别地，若 x 是搜索树的根节点，则 x 是割点当且仅当搜索树上存在至少两个子节点 y1，y2 满足以上条件。

模板：

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
const int maxn=100010;
int head[maxn],ver[maxn*2],Next[maxn*2];
int dfn[maxn],low[maxn],sta[maxn];
int n,m,tot,num,root;
bool cut[maxn];
void add(int x,int y)
{
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++num;
    int flag=0;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x])
            {
                flag++;
                if(x!=root||flag>1) cut[x]=1;
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
int main()
{
    cin>>n>>m;
    tot=1;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        if(x==y) continue;
        add(x,y),add(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) root=i,tarjan(i);
    }
    for(int i=1;i<=n;i++)
        if(cut[i]) printf("%d ",i);
}