我可以凭直觉看出这个假设是正确的，但在数学上我无法证明。任何帮助将不胜感激。
最佳答案
让这个图有n个顶点。
假设我们反转所有的边，那么我们试图证明存在一个出度为零的顶点。
如果不是，则只需从任何地方开始并沿着 n 条边行进(总是可能的，因为每个顶点的出度都不是零)。因此，我们访问了 n+1 个顶点 - 因此至少其中 2 个顶点必须相同(鸽子洞原则)，因此我们在您的无环图中找到了一个环。
关于algorithm - 如何证明有向无环图中至少存在一个入度为零的顶点？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33667865/