关于DFS的论断求证：同属一个SCC的节点是否每次DFS都在同一棵树中

该论断的正确性需要结合DFS的定义判断：

• 如果是指遍历全图的完整DFS（每次选任意未访问节点启动DFS，生成DFS森林，覆盖所有节点），则论断正确。
• 如果是指固定起始节点的单次DFS（仅遍历起始点可达的节点），则论断错误。

全图DFS场景下的正确性证明 #

必要性：若u、v同属一个SCC，则任意全图DFS运行中二者一定在同一棵DFS树 #

同一强连通分量的核心定义是u和v互相可达：

• 若某次DFS优先访问到u：由于u存在到v的路径，DFS在u的递归分支返回前，一定会遍历到路径上的所有节点（包括v），因此v会被纳入u所在的DFS树。
• 若某次DFS优先访问到v：同理，v到u的可达性保证u会被纳入v所在的DFS树。
  因此同SCC的节点永远会出现在同一棵DFS树中。

充分性：若任意全图DFS运行中u、v都在同一棵DFS树，则二者一定同属一个SCC #

我们用反证法推导：假设u、v不同属一个SCC，但所有全图DFS运行中二者都在同一棵树，必然存在矛盾。
u、v不同属SCC只可能是三类情况：

• 情况1：u可以到达v，但v无法到达u：我们可以构造DFS选点顺序：优先选择v作为第一个未访问节点启动DFS。由于v没有到u的路径，v所在的DFS树遍历完成后u仍未被访问。接下来选择u启动DFS，u遍历到v时v已经被标记为已访问，不会被纳入u的树，最终u、v分属不同树，和假设矛盾。
• 情况2：v可以到达u，但u无法到达v：和情况1对称，同样可以构造DFS让二者分属不同树，矛盾。
• 情况3：u、v互相不可达：构造DFS选点顺序：先选择u启动DFS，遍历完u可达的所有节点后，v仍未被访问。再选择v启动DFS，二者分属不同树，矛盾。
  综上，只要任意全图DFS中u、v都在同一棵树，二者必然互相可达，即属于同一个SCC。

固定起点DFS场景下的反例 #

如果限定DFS从固定节点启动，只遍历可达节点，论断不成立，反例如下：

有向图结构为 s→a, s→b, a→b，a和b不属于同一个SCC（b无法到达a），但所有从s出发的DFS运行中，a和b永远会出现在同一棵DFS树中，不符合论断的推导逻辑。

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