通过深度优先搜索算法生成有向图的DFS树，是否有可能存在横叉边数目等于Ω(n^2)的情况？
问题描述：
题中n代表树点。我现在能想到的就只有：有向图的最大边数为n(n-1)，但我不知道如何证明出Ω(n^2)？还是说这种情况并不可能？谢谢！
答
有具体的说明吗，什么题，什么场景
如果非要到n^2，那就往里填平行边呗，某个图的dfs树种存在横叉边的话，把这些横叉边添加到n^2规模再搜索不就是你要的了。
答
大概想了一下，似乎找不到Ω(n^2)的情况？应该是不可能。严格的证明我还要想想。