无向图割点+割边求法

1.关键概念

• 连通分量：无向图中互通的点
• 割点（Cut vertex）：删除以后联通分量变为两个或更多
• 割边（Cut edge）：同上
• 双联通问题：实现没有割点和割边的图
• 双联通分量：联通图中任意选择亮点，至少存在两条“点不重复”路径
  这里也就是说，对于双联通的图，图是相对“可靠的”，不会因关键节点断开而分裂成多个联通块，可以保持图的联通性

2.求割点

2.1 DFS + 暴力

删除每个点后用DFS求连通性，复杂度$O(V*V)$

2.2 深搜优先生成树

深搜优先生成树是根据对图的深搜顺序形成的树
概念：

• 树边：树上的边
• 回退边：在搜索过程中，因为vis冲突而不在访问的边

2.2.1 性质及解决思路

• 定理1:T的根节点s是割点，当且仅当s有两个或者更多的子节点

3. 求双联通分量

3.1 点双联通分量

一般使用Tarjan算法：

• 因为在DFS计算割点的过程中已经完成了对极大点双联通子图的访问

3.2 边双联通分量