Stoer-Wagner算法直接求无向图全局最小割，无需指定源汇点；其核心是迭代执行最大邻接搜索（确定动态s、t及当前割值）与缩点操作，共n−1轮，时间复杂度O(n³)。
Stoer-Wagner算法天生就不需要建源点或汇点——它直接求全局最小割，根本绕开了最大流框架。这是它和 Ford-Fulkerson、Dinic 等算法最本质的区别。
为什么不用指定 s 和 t？
算法依赖的关键引理是：对任意两个点 s 和 t，全局最小割要么把它们分开（此时就是 s-t 最小割），要么把它们放在同一侧（此时缩点不影响结果）。所以每次迭代只需“临时选一对”，用 max-weight adjacency（最大邻接搜索）找出当前图中某对点的 s-t 候选最小割，然后无脑缩点，把问题规模减一。重复 n-1 次，所有可能的分离都被覆盖过，最小值自然浮现。
max_adjacency_search 怎么隐式确定 s 和 t？
这个过程像 Prim 构建最大生成树，但不建树，只维护一个集合 A 和数组 dis[v]（表示 v 到当前 A 的边权和）：
- 初始任选一点加入
A，dis全为 0 - 每次从非
A中选dis[v]最大的点v加入A，并更新其余点的dis - 最后加入的点记为
t，它前一个加入的点记为s - 此时
dis[t]就是当前图的s-t最小割值，也是本轮候选全局最小割
注意：s 和 t 不是预设的，而是由贪心扩展顺序动态决定的；dis[t] 的物理意义是：把 t 单独拎出来时，它和其余所有点的连接总强度——这恰好等于把它和 s 分开所需的最小割容量。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
缩点操作怎么避免手动维护源汇逻辑？
缩点不是为了构造新流网络，而是拓扑简化：
- 删掉
s和t两个节点 - 新建一个节点
u，对每个剩余节点v，设cap[u][v] = cap[s][v] + cap[t][v] - 不引入任何方向性，不设置流量守恒约束，不跑任何增广路
整个过程完全在邻接矩阵（或邻接表+映射）上做原地合并，cap 始终是对称的。你甚至不需要显式构建新图，只需在下一轮 max_adjacency_search 中跳过已 del 的点，并让 dis 累加时自动包含合并后的边权。
容易被忽略的工程细节
真正卡住人的往往不是原理，而是边界和数值处理：
- 图必须连通，否则初始
dis[t]可能为 0，但全局最小割应是 0 —— 这本身合法，需允许输出 0 - 缩点后自环边（
s和t都连向同一v）会合并成一条边，但s和t之间的边权要丢弃（因为缩点时不再需要内部连接） - 若用邻接矩阵实现，
del[i] = true后，所有涉及i的循环必须跳过，否则dis会累加脏数据 - 初始化
dis必须清零，且每次新轮迭代前重置vis和dis，不能复用上一轮残留状态
缩点不是黑盒操作，它靠的是对边权可加性的信任；而 max_adjacency_search 的有效性，取决于你严格按“最大邻接”贪心推进——少一次更新、错一次比较，dis[t] 就不再是合法割值。
