From 0afac6dbf18f3c346c043146462b9fadf6aa795c Mon Sep 17 00:00:00 2001 From: =?utf8?q?=E9=9B=B7=E8=92=BB?= <34390285+hsfzLZH1@users.noreply.github.com> Date: Sun, 14 Jul 2019 18:56:19 +0800 Subject: [PATCH] Update scc.md MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 移动了两句话,合并了两句话 --- docs/graph/scc.md | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) diff --git a/docs/graph/scc.md b/docs/graph/scc.md index 8d5ca39a..66ab3b8d 100644 --- a/docs/graph/scc.md +++ b/docs/graph/scc.md @@ -31,10 +31,6 @@ Tarjan 发明了很多算法结构。光 Tarjan 算法就有很多,比如求 3. 横叉边(cross edge):红色边,它主要是在搜索的时候遇到了一个已经访问过的结点,但是这个结点 **并不是** 当前结点的祖先时形成的。 4. 前向边(forward edge):蓝色边,它是在搜索的时候遇到子树中的结点的时候形成的。 -一个结点的子树内结点的 DFN 都大于该结点的 DFN。 - -从根开始的一条路径上的 DFN 严格递增。 - 我们考虑 DFS 生成树与强连通分量之间的关系。 如果结点 $u$ 是某个强连通分量在搜索树中遇到的第一个结点,那么这个强连通分量的其余结点肯定是在搜索树中以 $u$ 为根的子树中。 $u$ 被称为这个强连通分量的根。 @@ -47,7 +43,9 @@ Tarjan 发明了很多算法结构。光 Tarjan 算法就有很多,比如求 1. $DFN[u]$ :深度优先搜索遍历时结点 $u$ 被搜索的次序。 2. $LOW[u]$ :设以 $u$ 为根的子树为 $Subtree(u)$ 。 $LOW[u]$ 定义为以下结点的 $DFN$ 的最小值: $Subtree(u)$ 中的结点;从 $Subtree(u)$ 通过一条不在搜索树上的边能到达的结点。 -显然,按照 DFS 搜索树的递归顺序, $LOW[u]$ 是单调递增的。 +一个结点的子树内结点的 DFN 都大于该结点的 DFN。 + +从根开始的一条路径上的 DFN 严格递增, LOW 严格非降。 按照深度优先搜索算法搜索的次序对图中所有的结点进行搜索。在搜索过程中,对于结点 $u$ 和与其相邻的结点 $v$ (v 不是 u 的父节点)考虑 3 种情况: -- 2.11.0