Nyaan さんの解説 とは別の方法で \(2\) 部グラフの最大マッチング問題に帰着する方法を紹介します．

公式解説 の冒頭で作られている \(2\) 部グラフを \(G = (V, E)\) として，\(G\) のコピーを \(2\) つ作って \(G_1 = (V_1, E_1)\), \(G_2 = (V_2, E_2)\) とします． さらに，? の各頂点 \(v \in V\) について，それらのコピー \(v_1 \in V_1\) と \(v_2 \in V_2\) を結ぶ辺を追加します． こうして作られたグラフ \(\tilde{G}\) も \(2\) 部グラフです．（同じ頂点のコピーどうしが結ばれるため，\(V_1\) と \(V_2\) で色が反転します．） さらに，\(\tilde{G}\) が完全マッチングを持つことと，\(G\) が「 2 の頂点をすべてカバーするマッチング」を持つことは同値 \((*)\) です． よって，\(\tilde{G}\) で最大マッチングを求め，それが完全マッチングであるかどうかを判定することで元の問題が解けました．

実装例 (C, 86 ms)

【 \((*)\) の証明】

\(G\) が「 2 の頂点をすべてカバーするマッチング」を持つとき，そのコピーを \(G_1\), \(G_2\) 内で取った後，マッチされずに残った ? の頂点どうしを追加辺を使ってマッチすれば，\(\tilde{G}\) の完全マッチングが得られます．

一方，\(\tilde{G}\) が完全マッチングを持つとき，2 の頂点はすべて \(G_1\), \(G_2\) それぞれの内部でマッチされていなければならないので，いずれか一方に制限して得られるマッチングは「 2 の頂点をすべてカバーするマッチング」となっています．