From 30ddf2b4ab8cfdd3fca60dc2b021b1252d64d5a8 Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Sun, 14 Jul 2019 06:54:20 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/graph/scc.md | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/docs/graph/scc.md b/docs/graph/scc.md index 1d9c3ded..8d5ca39a 100644 --- a/docs/graph/scc.md +++ b/docs/graph/scc.md @@ -44,8 +44,8 @@ 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)$ 通过一条不在搜索树上的边能到达的结点。 显然,按照 DFS 搜索树的递归顺序, $LOW[u]$ 是单调递增的。 @@ -70,7 +70,7 @@ Tarjan 发明了很多算法结构。光 Tarjan 算法就有很多,比如求 对于一个连通分量图,我们很容易想到,在该连通图中有且仅有一个 $DFN[u]=LOW[u]$ 。该结点一定是在深度遍历的过程中,该连通分量中第一个被访问过的结点,因为它的 DFN 值和 LOW 值最小,不会被该连通分量中的其他结点所影响。 -因此,在回溯的过程中,判定 $DFN[u]=LOW[u]$ 的条件是否成立,如果成立,则栈中从 $u$ 后面的结点构成一个 SCC 。 +因此,在回溯的过程中,判定 $DFN[u]=LOW[u]$ 的条件是否成立,如果成立,则栈中从 $u$ 后面的结点构成一个 SCC。 ### 实现 -- 2.11.0