与二分图有关的问题的解决思路之一。另一个是 flow。
Hall 定理：给定一个二分图，其中左部点集合为 \(L\)，右部点集合为 \(R\)。该二分图存在大小为 \(L\) 的匹配，当且仅当 \(\forall S \subseteq L, |S| \le |N(S)|\)。
Hall 定理推论：给定一个二分图，其中左部点集合为 \(L\)，右部点集合为 \(R\)。其最大匹配的大小为 \(|L| - \max_{S \subseteq L} |S|-|N(S)|\)。
不会证喵。
例题 1（Atcoder abc214_e）：