LGOJ P3388 【模板】割点（割顶）

LGOJ P3388 【模板】割点（割顶）

给定一个有向图（可能不联通），求这个图上所有的割点。所谓割点，就是在删除这个点之后，图的连通分量+1。

这里使用的是\(Tarjan\)算法——但是要注意，这里割点的\(Tarjan\)和求强连通分量的Tarjan是有区别的。区别还很多，主要是以下几个：

1. 是否是有向图；
2. \(LOW[]\)的含义；
3. 算法的写法；

首先明晰各个参量的含义：

\(DFN[]\)记录了当前节点在深度优先搜索时的时间戳的值；
\(LOW[]\)表示该节点和它的子树最早能够到达的时间戳；

选定一个根节点对图进行深度优先搜索，维护\(DFN[]\)和\(LOW[]\)两个数组。

同时加入对一个节点是否是割点的判断：

1. 如果当前节点是搜索时选定的根节点，如果其子节点的数量\(\geq 2\)，该节点是割点；
2. 如果当前节点非根节点，如果\(LOW[v] \leq DFN[u]\)，也即这个根节点\(v\)和其子树最早能到达的时间戳都达不到\(u\)的上面（即u的父以上的节点），那么如果去掉\(v\)这个图就会一分为二，所以\(v\)是割点；

注意：在割点算法的\(Tarjan\)函数中，如果某个节点在即将访问的时候已经被访问过了，那么\(LOW[]\)的更新方式必须是\(LOW[u]=min(LOW[u],DFN[v])\)；

但是在求强连通分量的算法中，\(LOW[]\)的更新方式可以是\(LOW[u]=min(LOW[u],DFN[v])\)，也可以是\(LOW[u]=min(LOW[u],LOW[v])\)，虽然两种写法求出来的LOW[]内部的值可能是不一样的，但是算法的运行结果是一样的。但是一般同一写作\(LOW[u]=min(LOW[u],DFN[v])\)。

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

inline int read()
{
    char c = getchar(); int x = 0;
    for (; !isdigit(c); c = getchar());
    for (; isdigit(c); c = getchar())
        x = x * 10 + c - '0';
    return x;
}
const int N=20005;
int n,m,DFN[N],LOW[N],ts,cnt,cut[N];

bool in[N];
vector<int> G[N];

void Tarjan(int u,int fa)
{
    int s=0;
    DFN[u]=LOW[u]=++ts;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(DFN[v]==0)
        {
            Tarjan(v,u);
            LOW[u]=min(LOW[v],LOW[u]);
            if(fa==0)s++;
            else if(LOW[v]>=DFN[u])cut[u]=1;
        }
        LOW[u]=min(LOW[u],DFN[v]);
    }
    if(s>=2&&fa==0)cut[u]=1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u=read();
        int v=read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1;i<=n;i++)if(DFN[i]==0)Tarjan (i,0);
    int ans=0;
    for(int i=1;i<=n;i++)if(cut[i])ans++;
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)if(cut[i])cout<<i<<' ';
    return 0;
}

LGOJ P3388 【模板】割点（割顶）

原文：https://www.cnblogs.com/kion/p/11865998.html