亚麻 一轮VO

3070742099 发表于 2019-12-11 02:17
E（V+E）

能解释下为什么吗？create graph用了O(V+E), 还有什么会增加space complexity吗？

vvict123 发表于 2019/12/11 05:50:48
能解释下为什么吗？create graph用了O(V+E), 还有什么会增加space complexity吗？

tarjan 算法等一轮dfs的这些是E+V, 暴力是说去除一条边 然后去看连通的情况，  要去n次 边 每次一个dfs 所以是e（e+v）

3070742099 发表于 2019-12-11 08:10
tarjan 算法等一轮dfs的这些是E+V, 暴力是说去除一条边 然后去看连通的情况，  要去n次 边 每次一个dfs 所 ...

是的，那这个不是time complexity吗？space complexity也是这样算吗？

vvict123 发表于 2019/12/11 08:15:09
是的，那这个不是time complexity吗？space complexity也是这样算吗？

还有dfs 栈空间 应该就没了