更新时间：2021-12-02 11:15
块（Block），图论中重要概念，是某一图中不含割点(cut-vertex)的极大连通子图。每一个图都可以被分割为一个或多个块。
A block of a graph G is maximal connected subgraph of G that has no cut-vertex.
If G itself is connected and has no cut-vertex, then G is a block.
1、同一个图中的两个块最多只能共享一个顶点，并且这个顶点必定是一个割点(cut-vertex)。
2、如果一个块包含多于两个顶点，那么这个块必定是2-连通的(2-connected)。
3、图G的块-割点图(The block-cutpoint graph)是一个二部图，一部分由割点组成，另一部分由块组成，它们之间存在边当且仅当割点是块的一部分。如果图G是连通的，那么它的块-割点图是一棵树。
深度优先搜索（DFS）
输入：一个连通图G
输出：图G的块划分
主要思想：建立图G的DFS树T，如果识别出了一个块就将其从T上删除；保持一个顶点为ACTIVE状态
初始化：选择一个根节点x∈V(G)；将x设为ACTIVE；设置T={x}
步骤：将当前状态为ACTIVE的点记作v
(1)如果v存在一个没有访问过的边vw:
1.1 如果w∉V(T)，那就将边vw加入树T，将vw标记为已访问，将w设为ACTIVE；
1.2 如果w∈V(T)，那说明w是v祖先，将vw标记为已访问。
(2)如果v的所有边都已经访问过了:
2.1 如果v≠x，并且选择v的父亲节点w，将w设为ACTIVE。在当前情况下，如果以v为根节点的T的子树T‘中不存在一条边连接到w的任意先祖，那么V(T‘)∪{w}就是一个块，将其记录并将T‘删除；
2.2 如果v=x，那么所有点都已经访问过了，算法终止。