algorithm - 基于罗宾斯定理的强方向图算法

Question

有人问我一个类似这样的问题:

Using depth-first search and Robbins' theorem, design and analyze an efficient algorithm to construct a strong orientation of a given undirected graph G. If none exist, output a bridge in G.

现在，我可以很容易地证明罗宾斯定理，它指出一个图是强可定向的，当且仅当它没有桥(即它是 2 边连接的)。给我的例子类似于罗宾斯在 1939 年的论文中给出的例子，该论文描述了他关于交通问题和单行道的同名定理。但是我不知道如何构建这个算法。
(好吧，并不是很茫然。如果我们做这样的事情会怎样:运行 DFS，使所有黑色边缘都朝一个方向，并使所有灰色边缘朝另一个方向。同时，测试每个顶点的 2-edge-connectivity。不过，这是纯粹的直觉，我不确定如何定义一致的方向性。)

Answer 1

无向图上的 DFS 仅产生树边和后边。将树边从祖先指向后代允许根到达所有其他节点。后边缘应该从后代到祖先定向，因为另一个方向被树边缘覆盖。如果你发现一个子树没有到子树祖先的后边，那么进入子树的边就是一座桥。否则，有一条从每个节点到根节点的路径，通过一些边重复转义当前子树到一个祖先，使有向图强连接。