割点 洛谷P3388 【模板】割点（割顶） 学习板子

在无向连通图中，删除一个顶点v及其相连的边后，原图从一个连通分量变成了两个或多个连通分量，则称顶点v为割点，同时也称关节点(Articulation Point)。一个没有关节点的连通图称为重连通图(biconnected graph)。若在连通图上至少删去k 个顶点才能破坏图的连通性，则称此图的连通度为k。

在介绍算法之前，先介绍几个基本概念

DFS搜索树：用DFS对图进行遍历时，按照遍历次序的不同，我们可以得到一棵DFS搜索树，如图(b)所示。
树边：（在[2]中称为父子边），在搜索树中的实线所示，可理解为在DFS过程中访问未访问节点时所经过的边。
回边：（在[2]中称为返祖边、后向边），在搜索树中的虚线所示，可理解为在DFS过程中遇到已访问节点时所经过的边。

eg:(a)中G7 是连通图，但不是重连通图。图中有三个关节点A、B 和G 。若删去顶点B 以及所有依附顶点B 的边，G7 就被分割成三个连通分量{A、C、F、L、M、J}、{G、H、I、K}和{D、E}。类似地，若删去顶点A 或G 以及所依附于它们的边，则G7 被分割成两个连通分量。


Tarjan: 观察DFS搜索树，我们可以发现有两类节点可以成为割点：

对根节点u，若其有两棵或两棵以上的子树，则该根结点u为割点；
对非叶子节点u（非根节点），若其子树的节点均没有指向u的祖先节点的回边，说明删除u之后，根结点与u的子树的节点不再连通；则节点u为割点。
对于根结点，显然很好处理；但是对于非叶子节点，怎么去判断有没有回边是一个值得深思的问题。

我们用dfn[u]记录节点u在DFS过程中被遍历到的次序号，low[u]记录节点u或u的子树通过非父子边追溯到最早的祖先节点（即DFS次序号最小），那么low[u]的计算过程如下：

下面是个板子

题目链接https://www.luogu.org/problem/show?pid=3388

题目背景

割点

题目描述

给出一个n个点，m条边的无向图，求图的割点。

输入输出格式

输入格式：
第一行输入n,m

下面m行每行输入x,y表示x到y有一条边

输出格式：
第一行输出割点个数

第二行按照节点编号从小到大输出节点，用空格隔开

输入输出样例

输入样例#1：
6 7
1 2
1 3
1 4
2 5
3 5
4 5
5 6
输出样例#1：
1
5
说明

n,m均为100000

tarjan 图不一定联通！！！

来自网上的一个板子

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n,m;
int head[100005];
int bel[100005];
int dfn[200005];
int low[200005];
int stack[100005];
int to[200005];
int nex[200005];
int fa[200005];
int tot;
int cnt=1;
bool cut[200005];
inline void add(int x,int y){
    ++tot;
    nex[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}
void tarjan(int p){
    int rd=0;
    dfn[p]=low[p]=++cnt;
    for(int i=head[p];i;i=nex[i]){
        int v=to[i];
        if(!dfn[v]){
            fa[v]=fa[p];
            tarjan(v);
            low[p]=min(low[p],low[v]);
            if(low[v]>=dfn[p]&&p!=fa[p])cut[p]=true;
             //非根且子树能达到的dfn最小的结点的时间>=自己的时间时
            //说明他的子树中最早能访问到的结点都比他后访问，只要不为根就一定是割点（注意根例外）
            if(p==fa[p]) rd++;
        }
        low[p]=min(low[p],dfn[v]);
    }
    if(p==fa[p]&&rd>=2)cut[fa[p]]=true;//入度>=2且为根的结点，因为一棵树的根一删不管有几棵子树肯定都不连通了
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    memset(dfn,0,sizeof(dfn));
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    int ans=0;
    for(int i=1;i<=n;i++)
    if(cut[i])ans++;
    printf("%d\n",ans);
    for(int i=1;i<=n;i++)
    if(cut[i])printf("%d ",i);
    return 0;
}