关于为什么要建有向边
查看原帖
关于为什么要建有向边
230141
Figo17楼主2021/11/18 16:45

酱紫

感觉题解区都没有很详细的证明;

如果把该图看作二分图的话,每一条婚姻断裂后,

Unsafe的充要条件是能找到新的增广路。

因此匹配的边在寻找增广路的过程中成为了有向边;

而存在增广路的充要条件,

就是存在某个强连通分量使得最初的夫妻均在其中。

大概像上面画的那样。

2021/11/18 16:45
加载中...