给定有向无环图，制定最少加边策略实现所有顶点间双向可达

要让DAG中所有顶点两两之间存在双向路径，本质是把DAG转化为强连通图，以下是一种实用的策略：

1. 先对DAG做拓扑排序，明确顶点的先后依赖关系。
2. 找出图中所有入度为0的顶点（源点集合S）和出度为0的顶点（汇点集合T）：
   • 源点是没有任何前驱的节点，汇点是没有任何后继的节点，这些节点是导致图无法强连通的核心原因。
3. 根据两个集合的大小执行边添加操作：
   • 如果图中只有1个顶点：无需添加任何边。
   • 如果|S|=1且|T|=1：添加一条边，把唯一的汇点指向唯一的源点，形成闭合环后整个图就强连通了。
   • 其他情况：取max(|S|, |T|)作为需要添加的最少边数。具体操作可按拓扑顺序将源点和汇点配对连接，比如把第i个汇点指向第i个源点；若其中一个集合更大，剩余节点可连接到另一个集合中的任意节点（比如把剩余源点指向最后一个汇点，或剩余汇点指向第一个源点）。

示例说明 #

比如题目中提到的示例DAG，假设其源点集合S有2个节点、汇点集合T也有2个节点，只需添加2条边将两个汇点分别指向对应的源点，就能让整个图强连通，符合最优解要求。

特殊场景处理 #

• 当图中没有任何边时（所有节点都是源点也是汇点），此时|S|=|T|=n（n为节点数），只需将这些节点连成一个环（添加n条边），即可实现强连通。

内容的提问来源于stack exchange，提问作者banan