King's Quest

link
问题倒是不难想，你考虑这样一个样子。

我们想要粉边能取，由于这是一个完美匹配，那么一定是有一条交错树组成的偶环包括这条边。由于这是二分图，那么边数肯定是偶数，所以跑个强连通就行了。
值得一提的是，对于男孩 \(x\)，强连通中不一定每个点 \(y\) 都合法，前提是 \(x\) 与 \(y\) 右边。

extended：\(n\) 个男孩，\(m\) 个女孩，这时能完备匹配有两种情况：1.偶环 2.偶链，这时我们在男孩的部中建出虚点，将没匹配的女孩和匹配了的男孩与之相连，目的是将情况 2 弄成情况 1 以应对普适性问题。