71-算法解析及优化拓展

7.10.6　算法解析及优化拓展

1．算法复杂度分析

（1）时间复杂度：主要采用7.4.5节的最小费用最大流算法MCMF，因此总的时间复杂度为O(VE²)，其中V为结点个数，E为边的数量。

（2）空间复杂度：使用了一些辅助数组，因此空间复杂度为O(V）。

2．算法优化拓展

对于一个连通图，如果任意两点至少存在两条“点不重复”的路径，则说这个图是点连通图的（一般称为双连通，biconnected）。这个要求等价于任意两条边都在同一个简单环上。题的要求提取出来后，可得本质思路就是求在一个图中的最大环，这正是双连通的定义。因此可以用Tarjan算法来求解，时间复杂度降了很多，有兴趣的读者可以看看。