给定一个有向无环图，创建一个策略，使所有可能的顶点之间存在双向路径

Question

给定一个有向无环图，创建一个策略，使所有可能的顶点之间存在双向路径

您可以通过添加边缘来实现这一点。提出一种通过添加尽可能少的边来解决此问题的策略 输入图上的顶点可以没有边。

示例： 为了以最有效的方式求解该图，我们只需要添加 2 条边：

请记住，算法不需要完美，也不需要编写任何代码（除非你想:)）。

Answer 1

考虑一个有 m 个入度为 0 的顶点和 n 个出度为 0 的顶点的 DAG：

显然，您需要添加 m 个传入入度 0 顶点的边，以及 n 个从出度 0 顶点传出的边，因此您可以期望的最好结果是 max(m,n) 个新边。我们可以实现这一目标。

首先，如果 m > n，则连接入度为 0 的顶点，直到 m = n。否则连接出度 0 的顶点直到 m = n。

现在我们有 m=n，我们将维持它：

• 找到一个入度为 0 的顶点，并且不会到达所有出度为 0 的顶点。如果没有，则将出度为 0 的顶点任意连接到入度为 0 的顶点，就可以了全部完成。
• 否则，将其确实到达的出度顶点连接到其未到达的入度0顶点。这将 m 和 n 减少 1。
• 重复直到完成。