Stoer–Wagner 算法

[giscus[bot]]

Stoer–Wagner 算法

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

https://oi-wiki.org/graph/stoer-wagner/

[caijiMK]

则对任意点 $s$，一个 $s$ 到 $t$ 的割即为 $w(t)$。

这里错了吧，必须满足 $s$ 是 $t$ 前最后一个加入到 $A$ 中的点，只有这样才能保证 $s$ 和 $t$ 不在同一连通块，进而保证 $t$ 会被激活。

因此这句话：

由于 $\operatorname{pos}(s) < \operatorname{pos}(t)$，并且 $s, t$ 不在同一连通块，因此 $t$ 会被激活，由此可以得出 $w(A_t, t) \le w(C_t) = w(C)$。

也有问题，应该是对于所有满足 $s, t$ 不再同一连通块的割都满足 $t$ 会被激活，由此可以得出 $w(A_t, t) \le w(C_t) = w(C)$。