【算法】二分图最大匹配中的 可行/必经 点/边 – foreverpiano

在残量网络跑 SCC, 考虑边 $ (x, y) $ 或者点 $ x, y$

可行边: 要求 $ (x,y) $ 是匹配边或 $ (x,y) $是非匹配边，但 $ x $ 和 $ y $ 处在同一个 SCC 中。

必经边: 要求 $ (x,y) $ 是匹配边且 $ x $ 和 $ y $ 不在同一 SCC 中。

可行点: $ x $ 的出边至少有一条是可行边。

非必经点: 从 S 出发只走 cap = 1 的边能到达 $ x $ ， 或者从 T 出发只走 cap = 0 的边能到达 $ y $ 。

可行点/必经点 不知道有没有更简单做法。