拜谢陈老师的 PPT！！！

无向图

割点

若点 \(x\) 不为搜索树的根节点，则 \(x\) 是割点当且仅当搜索树上存在一个 \(x\) 的子节点 \(y\) 满足： \(dfn_x\le low_y\)。特别地，当 \(x\) 是搜索树的根节点时，则 \(x\) 是割点当且仅当有两个点 \(y_1,y_2\) 满足上述条件。

割边

边 \((x,y)\) 是桥当且仅当搜索树上存在 \(x\) 的子节点 \(y\) 满足：\(dfn_x<low_y\)。

\(\text{v-DCC}\)

为求出点双连通分量，则需在 Tarjan 算法的过程中维护一个栈，并按如下操作维护：

1. 将第一次被访问到的点入栈。
2. 当割点判定法则成立时：从栈顶开始弹，直到弹出 \(y\)，且弹出的所有点都与 \(x\) 构成一个 \(\text{v-DCC}\)。

\(\text{e-DCC}\)

求 \(\text{e-DCC}\) 比 \(\text{v-DCC}\) 简单多了。

求出所有割边，然后再跑一遍 dfs，过程中不走割边，每个连通块就都是一个 \(\text{e-DCC}\)。

\(\text{v-DCC}\) 缩点

\(\text{v-DCC}\) 和割点都分别看做一个点，然后根据原图关系连边。

\(\text{e-DCC}\) 缩点

\(\text{e-DCC}\) 作为点，割边作为边，连边即可。

有向图

我不会。