概述
在一个无向图中，若删除某个点u后连通分量数目增加，则称点u为该无向图的一个割点(cut vertex)
引理
无向连通图DFS树
从一个节点出发进行DFS，将后访问的结点设为前访问结点的孩子，DFS经过的边叫做DFS树的树边(tree edge)，第一次处理时从后代(descendant)指向祖先(ancestor)的边叫做返祖边(back edge)
无向连通图的DFS树只存在树边和返祖边，不存在前向边(forward edge)和横叉边(cress edge)（在有向弱连通图中会讲到，前向边是结点指向其非孩子后代的边，横叉边是从一个子树指向另一个子树的边）
证：1、不存在回边：无向图的边无方向，故不存在回边（无重边时）
2、不存在横叉边：假设有横叉边(u,v)，假设u比v先访问，则DFS是一定会通过u访问到v，进而访问到它的祖先及子树（貌似不是很严谨？）
定义
dfn[u]表示进入结点u的时间（相对时间戳）
low[u]表示点u及其后代通过返祖边可以访问到的dfn值最小（高度最高）的结点的dfn值
算法
- 从起点开始DFS
- 访问一个节点，初始化其dfn值和low值均为当前时间戳（每个结点初始化可以到达dfn指最小（高度最高）的结点是自己）
- 枚举与当前结点相连的目标结点
- 若目标结点已访问过（是当前结点的祖先），更新当前结点的low值（low[u]=min(low[u],dfn[v])）
- 若目标结点未访问过（是当前结点的孩子），则对目标结点DFS，并在回溯后用目标结点的low值更新当前结点的low值（low[u]=min(low[u],low[v])）
- 判断当前结点是否为割点
- 若当前结点为根节点，当且仅当当前结点有不少于两个子树时当前结点为割点
- 若当前结点为非根节点，当且仅当当前结点有不少于一个孩子的low值不小于当前结点的dfn值
理解
若当前结点为根节点，当且仅当当前结点有不少于两个子树时当前结点为割点
因为无向连通图的DFS树无横叉边，所以显然当根节点有不少于两个子树时当前结点为割点
若当前结点为非根节点，当且仅当当前结点有不少于一个孩子的low值不小于当前结点的dfn值
若孩子的low值小于当前结点的dfn值，说明上（当前结点的祖先）下（当前结点的后代）在树边之外有边相连，删去当前结点仍连通（不增加连通分量的数量）。因为每个子树均独立，所以当且仅当当前结点至少有一个孩子的low值≥当前结点的dfn值时，当前结点为割点
此处用图象记忆可以加强理解且不易写错
模板
写代码的时候有个2小tips：
- 对于每个结点，我们只需要当前结点的low值和其子树中结点的low值，且low值是不断向上（由孩子到父亲）更新的，所以我们不需要将low值存放在数组中，只需要写成DFS返回值即可。
- 判断一个节点有没有访问过，只需要看其dfn值是否为0，为0则为访问过，不为0则访问过（置过时间戳）
另外模板中无向图不一定连通，所以要将所有的节点都扫描一遍，从未访问过结点的开始DFS即可
代码如下：
1 #include<cstdio> 2 #include<algorithm> 3 using namespacestd; 4 int dfn[1000001];//保存时间戳 5 int dfs_clock;//当前时间 6 int ans[1000001],num;//保存答案 7 structedge 8 { 9 intto,pre; 10 }edges[2000001]; 11 int head[1000001],tot;//邻接矩阵存图 12 int tarjan(int x,int fa)//tarjan求割点 13 { 14 int lowu=dfn[x]=++dfs_clock;//初始化low和dfn 15 int child=0,pd=0;//孩子数，是否有子树的low值不小于当前结点的dfn值 16 for(int i=head[x];i;i=edges[i].pre)//扫描所有的边 17 if(!dfn[edges[i].to])//目标结点未访问过（树边） 18 { 19 ++child; 20 int lowv=tarjan(edges[i].to,x);//目标结点的low值 21 if(lowv>=dfn[x])//目标结点low不小于当前结点dfn，当前结点是割点 22 pd=1; 23 lowu=min(lowu,lowv);//更新lowu 24 } 25 else if(edges[i].to!=fa)//目标结点未访问过（返祖边） 26 lowu=min(lowu,dfn[edges[i].to]); 27 if(x==fa&&child>1)//根节点的子树不少于2个 28 ans[++num]=x; 29 else if(x!=fa&&pd)//非根节点至少有一个子树low值不小于当前结点的dfn值 30 ans[++num]=x; 31 returnlowu; 32 } 33 void add(int x,int y)//邻接表存边 34 { 35 edges[++tot].to=y; 36 edges[tot].pre=head[x]; 37 head[x]=tot; 38 } 39 intmain() 40 { 41 intn,m; 42 scanf("%d%d",&n,&m); 43 for(int i=1;i<=m;i++) 44 { 45 intx,y; 46 scanf("%d%d",&x,&y); 47 add(x,y),add(y,x); 48 } 49 for(int i=1;i<=n;i++)//遍历n个点tarjan 50 if(!dfn[i]) 51 tarjan(i,i); 52 sort(ans+1,ans+1+num); 53 printf("%d ",num); 54 for(int i=1;i<=num;i++) 55 printf("%d ",ans[i]); 56 printf(""); 57 return 0; 58 }
洛谷的数据范围有毒！n,m不止10^5！大家打模板时要把数组开成10^6！