已知有向无环图，新增边是否会形成环？请求验证我的解法正确性

没错，这个思路是完全靠谱的，咱们来拆解一下背后的逻辑：

• 核心原理：原已知是无环有向图，添加边 F->T 后如果出现环，这个环必然包含这条新边。也就是说，环的结构一定是 F → T → ... → F——这就意味着原图里必须存在一条从 T 到 F 的路径。
• 反向验证：如果原图中从 T 出发能遍历到 F，那加上新边 F->T 就直接构成了闭环；如果遍历不到，那添加这条边后整个图依然保持无环状态，因为原图本身没有环，新边也不会和原有路径形成循环。

举两个直观的例子：

• 假设原图有路径 T → A → B → F，那从T遍历能到F，添加 F->T 后就出现了环 F→T→A→B→F，此时你的方法会正确返回 true。
• 如果原图里T和F之间没有任何可达路径，或者只有F到T的单向路径（原图无环，所以这条路径不会绕回F），那添加 F->T 后只是多了一条单向边，不会形成环，方法返回 false。

小补充：遍历的时候用DFS或者BFS都可以，只要是能检测节点间可达性的算法都适用，你可以根据图的规模选择效率更优的实现方式。

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