关于 DFS 的说法，是真的吗？
A claim regarding DFS, is it true?
在解决有关 DFS 的问题时，我注意到一些我无法正式证明或找到矛盾示例的东西。
让我们考虑一个有向图g
u, v 在同一个 SCC（强连接组件）中当且仅当 u, v 在每个 运行 DFS 中都在同一个 DFS 树中。
我的说法正确吗？
是的，这是真的。
如果u和v在同一个强连通分量中，则存在从u到v，从v到u的路径。考虑 u 出现的任何 DFS，并考虑（矛盾）从 u 到 v 的路径上的第一个顶点没有出现在 DFS 的 运行 中。但是在这个确实出现的路径之前的路径上有一个顶点，以及从那个顶点到没有出现的那个的边。但这是一个矛盾，因为 DFS 的工作方式，所以从 u 到 v 的路径上的每个顶点都出现在 DFS 中，因此 v 出现在 DFS 中。 （我们可以通过交换 u 和 v 来进行相同的论证）。
相反，假设在每个DFS中u出现v（反之亦然）。但是从 u 开始的 DFS 包括 v，这意味着有一条从 u 到 v 的路径。（同样，我们可以应用对称性来获得相同的 u 和 v 交换）。
在解决有关 DFS 的问题时，我注意到一些我无法正式证明或找到矛盾示例的东西。
让我们考虑一个有向图g
u, v 在同一个 SCC（强连接组件）中当且仅当 u, v 在每个 运行 DFS 中都在同一个 DFS 树中。
我的说法正确吗？
是的，这是真的。
如果u和v在同一个强连通分量中，则存在从u到v，从v到u的路径。考虑 u 出现的任何 DFS，并考虑（矛盾）从 u 到 v 的路径上的第一个顶点没有出现在 DFS 的 运行 中。但是在这个确实出现的路径之前的路径上有一个顶点，以及从那个顶点到没有出现的那个的边。但这是一个矛盾，因为 DFS 的工作方式，所以从 u 到 v 的路径上的每个顶点都出现在 DFS 中，因此 v 出现在 DFS 中。 （我们可以通过交换 u 和 v 来进行相同的论证）。
相反，假设在每个DFS中u出现v（反之亦然）。但是从 u 开始的 DFS 包括 v，这意味着有一条从 u 到 v 的路径。（同样，我们可以应用对称性来获得相同的 u 和 v 交换）。