From 82326e09c2b8a9d47a274de50f0d29688870fbd6 Mon Sep 17 00:00:00 2001 From: Ir1dXD Date: Sun, 14 Jul 2019 19:05:20 +0800 Subject: [PATCH] Update scc.md --- docs/graph/scc.md | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/docs/graph/scc.md b/docs/graph/scc.md index 59510398..5be6c42c 100644 --- a/docs/graph/scc.md +++ b/docs/graph/scc.md @@ -40,8 +40,9 @@ Tarjan 发明了很多算法结构。光 Tarjan 算法就有很多,比如求 ### Tarjan 算法求强连通分量 在 Tarjan 算法中为每个结点 $u$ 维护了以下几个变量: -1\. $DFN[u]$ :深度优先搜索遍历时结点 $u$ 被搜索的次序。 -2\. $LOW[u]$ :设以 $u$ 为根的子树为 $Subtree(u)$ 。 $LOW[u]$ 定义为以下结点的 $DFN$ 的最小值: $Subtree(u)$ 中的结点;从 $Subtree(u)$ 通过一条不在搜索树上的边能到达的结点。 + +1. $DFN[u]$ :深度优先搜索遍历时结点 $u$ 被搜索的次序。 +2. $LOW[u]$ :设以 $u$ 为根的子树为 $Subtree(u)$ 。 $LOW[u]$ 定义为以下结点的 $DFN$ 的最小值: $Subtree(u)$ 中的结点;从 $Subtree(u)$ 通过一条不在搜索树上的边能到达的结点。 一个结点的子树内结点的 DFN 都大于该结点的 DFN。 -- 2.11.0