有向图母顶点求解：两种DFS实现为何一个触发TLE？

给定有向图寻找母顶点（即能到达所有其他顶点的顶点）的场景下，你提供的两个DFS实现逻辑看似仅count++的位置不同，却导致一个超时（TLE）一个正常通过，核心原因在于count操作时机引发的性能差异，具体分析如下：

两个DFS的核心差异 #

两种实现的唯一区别是count++的执行时机：

• 超时的DFS：处理完当前节点的所有邻接点、递归返回后才执行count++
• 正常通过的DFS：标记当前节点已访问后，立刻执行count++，再处理邻接点

超时的根本原因 #

从逻辑上看，两个DFS最终计算出的count值都是正确的（每个被访问的节点都会让count加1），但性能差异来自于内存访问效率和编译器优化空间：

• 正常通过的DFS中，count++在进入节点时立即执行，后续递归调用仅在访问新节点时修改count。编译器可将count优化到CPU寄存器中，减少内存读写开销，大幅提升执行速度。
• 超时的DFS中，count++在所有递归返回后执行。每次递归返回时都需要从内存读取count、修改后再写回，频繁的内存访问会显著增加运行时间。当测试用例的图规模较大（比如顶点数上万、边数极多）时，这种开销累积会触发超时限制。

此外，递归返回阶段的连续count操作还可能降低缓存命中率，进一步加剧性能损耗。

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