萌新刚学Tarjan，啥也不会，肯定一堆错，请大佬指正谢谢
前置
强连通
- 强连通：
在不是强连通图的有向图\(G\)内，其顶点\(u\),\(v\)两个方向上都存在有向路径，则\(u\)和\(v\)强连通
- 强连通图：
对于有向图 \(G\) ，若\(G\)中任意两个结点连通，则称有向图\(G\)强连通。
- 强连通分量：
有向图的极大强连通子图
对于\(G\)的极大强连通子图\(S\)，添加任意顶点都会导致\(S\)失去强连通的属性
DFS生成树
DFS生成树主要有\(4\)种边：
- 树边：黑色边，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边
- 反祖边：红色边（\(7 \rightarrow 1\) ）指向祖先结点的边
- 横叉边：蓝色边（\(9 \rightarrow 7\)）在搜索的时候遇到了一个已经访问过的结点，这个结点并不是当前结点的祖先
- 前向边：绿色边（\(3 \rightarrow 6\) ）搜索的时候遇到子树中的结点的时候形成的
若结点\(u\)是某个强连通分量在搜索树中遇到的第一个结点(就是根)，那么这个强连通分量的其余结点肯定是在DFS搜索树中以\(u\)为根的子树中。
正文
桥
割点
强连通分量
维护变量：
-
\(\textit{dfn}_u\) ：深度优先搜索遍历时结点 \(u\) 被搜索的次序。
-
\(\textit{low}_u\) ：在 \(u\) 的子树中能够回溯到的最早的已经在栈中的结点。设以 \(u\) 为根的子树为 \(\textit{Subtree}_u\) 。 \(\textit{low}_u\) 定义为以下结点的 \(\textit{dfn}\) 的最小值： \(\textit{Subtree}_u\) 中的结点；从 \(\textit{Subtree}_u\) 通过一条不在搜索树上的边能到达的结点。
一个结点的子树内结点的 \(\textit{dfn}\) 都大于该结点的 \(\textit{dfn}\)。
从根开始的一条路径上的 \(\textit{dfn}\) 单调递增，\(\textit{low}\) 单调不下降。
算法
按照 dfs 序对所有结点进行搜索，维护每个点的 \(\textit{dfn}\) 与 \(\textit{low}\) ，让搜索到的结点入栈。每找到一个强连通元素，就按照该元素包含结点数目让栈中元素出栈。搜索过程中，对于结点 \(u\) 和与其相邻的结点 \(v\)(\(v\) 不是 \(u\) 的父节点)进行分类讨论：
-
\(v\) 未被访问：继续对 \(v\) 进行dfs。在回溯过程中，用 \(\textit{low}_v\) 更新 \(\textit{low}_u\) 。因为存在从 \(u\) 到 \(v\) 的直接路径，所以 \(v\) 能够回溯到的已经在栈中的结点， \(u\) 也一定能够回溯到。
-
\(v\) 被访问过，在栈中：根据 low 值的定义，用 \(\textit{dfn}_v\) 更新 \(\textit{low}_u\) 。
-
\(v\) 被访问过，不在栈中：说明 \(v\) 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。