一些概念
连通:无向图中的任意两点都可以互相到达。
强连通:有向图中的任意两点都可以互相到达。
连通分量:无向图的极大连通子图。
强连通分量:有向图的极大强连通子图。
DFS 生成树:对一张图进行深度优先遍历得到的生成树。
树边:在 DFS 生成树上的边。
前向边:由子树的根连向子树内的非树边。
返祖边:由结点连向其祖先的边。
横叉边:除上面三种边以外的边,也就是在两棵不相交子树之间的边。
割点:无向图删除某个点及其为端点的所有边后,若图的连通块数量增加,则该点是图的一个割点。
割边(桥):无向图删除某条边后,若图的连通块数量增加,则该边是图的一条割边。
点双连通图:不存在割点的无向连通图。
边双连通图:不存在割边的无向连通图。
点双连通分量:无向图的极大点双连通子图。
边双连通分量:无向图的极大边双连通子图。