From 79256946086e34458a67e29006fb00f8b7cf4e18 Mon Sep 17 00:00:00 2001 From: 24OI-bot <15963390+24OI-bot@users.noreply.github.com> Date: Sun, 14 Jul 2019 06:21:04 -0400 Subject: [PATCH] style: format markdown files with remark-lint --- docs/graph/scc.md | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/docs/graph/scc.md b/docs/graph/scc.md index d0d76f55..d5504a7e 100644 --- a/docs/graph/scc.md +++ b/docs/graph/scc.md @@ -37,15 +37,15 @@ Tarjan 发明了很多算法结构。光 Tarjan 算法就有很多,比如求 我们考虑 DFS 生成树与强连通分量之间的关系。 -如果结点 $u$ 是某个强连通分量在搜索树中遇到的第一个结点,那么这个强连通分量的其余结点肯定是在搜索树中以 $u$ 为根的子树中。$u$ 被称为这个强连通分量的根。 +如果结点 $u$ 是某个强连通分量在搜索树中遇到的第一个结点,那么这个强连通分量的其余结点肯定是在搜索树中以 $u$ 为根的子树中。 $u$ 被称为这个强连通分量的根。 反证法:假设有个结点 $v$ 在该强连通分量中但是不在以 $u$ 为根的子树中,那么 $u$ 到 $v$ 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边,然而这两条边都要求指向的结点已经被访问过了,这就和 $u$ 是第一个访问的结点矛盾了。得证。 ### 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]$ 是单调递增的。 @@ -105,7 +105,7 @@ Kosaraju 算法依靠两次简单的 DFS 实现。 第二次 DFS,对于反向后的图,以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点,选取标号最大的,重复上述过程。 -两次 DFS 结束后,强连通分量就找出来了,Kosaraju 算法的时间复杂度为 $O(n+m)$ +两次 DFS 结束后,强连通分量就找出来了,Kosaraju 算法的时间复杂度为 $O(n+m)$ ### 实现 -- 2.11.0