线性时间算法使图形强烈连接

Question

我们有一个弱无环图.

此外,我们给出一个集合A,它保存具有度数为零的G的顶点,以及一个集合B,其保持具有度数为零的顶点.(A的大小小于B的大小).

最重要的是,我们也知道如果A和B中的项目具有特定的顺序(例如A = a1,a2,...,am和B = b1,b2,...,bn),则dFS从ai开始访问bi(1≤i≤m).

有可能设计一个线性时间算法,通过添加尽可能少的边来使G强连接吗？

Answer 1

添加弧 b _j -> a _j+1 (j = 1, ..., m-1) 和弧 b _j -> a ₁ (j = m, ..., n)。

结果图是强连接的，因为 a 和 b 通过添加的弧和从 a _i到 b _i的路径强连接，并且对于每个节点 x，存在 i，j 使得原始图中存在从a _{i到 x 以及原始图中从 x 到 b j}的路径。

我们不能使用更少的弧，因为必须将传出弧添加到 b ₁ , ..., b _n中的每一个中。