P215's Solution

> [**Hall 定理：**](https://oi-wiki.org/graph/graph-matching/graph-match/#hall-%E5%AE%9A%E7%90%86)对于一个左部点个数不多于右部点个数的二分图 $G$，设 $N(S)$ 代表 $G$ 中与左部点集合 $S$ 中至少一个点有连边的右部点的集合，则 $G$ 存在完美匹配的充分必要条件是，对于任意的非空左部点集合 $S$，总有 $|N(S)| \ge |S|$。

• 68 次浏览
• 2025-12-10 21:55:12