检查有向图是否牢固连接的算法

当然，Tarjan的强连接组件算法（或Gabow的变体）就足够了；如果只有一个强连接的组件，则该图是强连接的。

两者都是线性时间。

与常规深度优先搜索一样，您可以跟踪每个节点的状态：新建，可见但仍处于打开状态（位于调用堆栈中）以及可见并完成。此外，您还可以存储首次到达节点时的深度，以及从节点可到达的最低深度（完成节点后便知道这一点）。如果最低可到达深度等于其自身深度，则节点是牢固连接的组件的根。即使从根到节点的深度不是最小的深度，此方法也有效。

要仅检查整个图是否是单个SCC，请从任何单个节点启动dfs，完成后，如果最低可到达深度为0，并且访问了每个节点，则整个图将牢固连接。