题解 P3388 【【模板】割点（割顶）】
简介一下割点，给自己复习一下，也是给像我一样的蒟蒻介绍一下割点
首先，什么是割点？
在浏览其他题解之后我知道割点
定义： 去掉无向联通图的某个点后，此图不连通，该点为割点
然后就是怎么求：
如图，我们将一张图抽象如上，1表示图的上部，5表示下部，中间由环相连。
我们用dfn[x]表示x被访问到的时间，low[x]表示它所在的那一坨的最小值 （感性理解一下）
我们从点1开始dfs，记录每一个点的时间戳，然后去搜所有没有搜过的，如果，他的儿子的最上面的时间戳（low[v]）
low[v]>=dfn[x]说明v最早也是在x及之后了，也就意味着x上面的与v只能通过x相连，也就是说，只要x上面有（x不为本组祖先），那么x就是割点
如果x是祖先呢？
那我们将x找到一个儿子便让x的儿子++，并让儿子搜一遍（保证和此儿子联通的都被搜过），那么下次找到的儿子就是和此儿子不连通的，那么只要把x去掉，他两个儿子就不连通了，所以，x为割点
不理解上面的算法结合图看，把①去掉，2,3这两个儿子就不连通了
还有一个问题：大佬都说这里low要这样写：low[x]=min(low[x],dfn[v])
至于为什么不像强联通分量里一样，写low[x]=min(low[x],low[v])呢？
因为强联通里只要在强联通中，怎么连边都可以（我们又不会在强联通中割点），但割点不行，我们不能随便连边，low[x]=min(low[x],low[v])表示所有v都连与最先祖先的上，如下图1，但很明显，3,4,5并没有这一条路，所以如果你这么写，代码会认为有这一条路，从而出错
当然，由图的关系得到的low并不会有假边所以写low[x]=min(low[x],low[v])（不理解看代码）
实际：
写low[x]=min(low[x],low[v])：
代码：
void tag(int x,int zx)
{
int kid=0;
dfn[x]=low[x]=++tim;
for(int i=head[x];i;i=p[i].next)
{
int v=p[i].to;
if(!dfn[v])
{
tag(v,zx);
low[x]=min(low[v],low[x]); //是有真边构成，不用改
if(low[v]>=dfn[x]&&x!=zx) cut[x]=1;//后面无法通过别的方法连接到前面，是割点
if(x==zx) kid++;
}
low[x]=min(low[x],dfn[v]); //要改的指这个
}
if(kid>1&&x==zx) cut[x]=1; //祖先有两个+的孩子，是割点
}完整ac代码：（高清无码）
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,m;
struct edge
{
int next,to;
}p[N];
int head[N],num;
void ad(int x,int y)
{
p[++num].next=head[x];
p[num].to=y;
head[x]=num;
}
int dfn[N],low[N],tim,cut[N];
void tag(int x,int zx)
{
int kid=0;
dfn[x]=low[x]=++tim;
for(int i=head[x];i;i=p[i].next)
{
int v=p[i].to;
if(!dfn[v])
{
tag(v,zx);
low[x]=min(low[v],low[x]);
if(low[v]>=dfn[x]&&x!=zx) cut[x]=1;
if(x==zx) kid++;
}
low[x]=min(low[x],dfn[v]);
}
if(kid>1&&x==zx) cut[x]=1;
}
int ans;
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ad(x,y);
ad(y,x);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tag(i,i);
for(int i=1;i<=n;i++) ans+=cut[i];
printf("%d\n",ans);
for(int i=1;i<=n;i++)
if(cut[i]) printf("%d ",i);
return 0;
}
2020.1.19
更新：
今天又写了一下发现了一个问题：
正确
for(int i=head[u];i;i=p[i].next)
{
int v=p[i].to;
if(!dfn[v])
{
taj(v,zx);
low[u]=min(low[u],low[v]);
if(u==zx) kid++;
if(low[v]>=dfn[u]&&u!=zx) cut[u]=1;
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}错误
for(int i=head[u];i;i=p[i].next)
{
int v=p[i].to;
if(!dfn[v])
{
taj(v,zx);
low[u]=min(low[u],low[v]);
if(u==zx) kid++;
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);
if(low[v]>=dfn[u]&&u!=zx) cut[u]=1;
}就是这个判断的时候，一定是要
只有直接儿子才可以按if(low[v]>=dfn[u]&&u!=zx) cut[u]=1;判，毕竟人家就是这么走的，但是如果是间接儿子，那么，实际上它应该是从别处走来的，所以这么写是错的