二部グラフの最大マッチングを用いた、別の解法を紹介します。

二部グラフの最大マッチングは最大流を用いて解くことができます。

頂点集合が \(U, V\) の二つの独立集合に分割できるものとします。 また、 \(u_i \in U, v_j \in V\) とします。 このとき、超頂点 \(S, T\) を追加し、 \(S \rightarrow u_i, u_i \rightarrow v_j, v_j \rightarrow T\) に容量 \(1\) の辺を貼ったグラフにおける最大流は最大マッチングに一致することが知られています。 (参考: 実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！‬ )

最大マッチングを求めた後の残余グラフを \(G'\) とします。 このとき、 \(G'\) において辺 \(u_i \rightarrow S\) が存在するならば頂点 \(u_i\) がマッチングに使われていることになります。

頂点 \(u_i\) を取り除く場合を考えましょう。

辺が \(S \rightarrow u_i\) の向きであるならば \(u_i\) はマッチングに使われていないので、取り除いても最大マッチングは変わりません。

辺が \(u_i \rightarrow S\) の向きであるとき、もしも \(S\) を始点、 \(u_i\) を終点とするパスが存在するならば、そのパスに \(S\) を加えたサイクル上のパスの向きを全て反転することで辺を \(S \rightarrow u_i\) の向きにすることができます。 逆にそのようなパスが存在しなければ、 \(u_i\) を取り除くことで最大マッチングが必ず \(1\) 減少します。

従って、頂点 \(u_i\) を取り除いても最大マッチングが変化しない必要十分条件は、残余グラフ \(G'\) 上で \(S\) から \(u_i\) に到達するパスが存在することであり、これは幅優先探索などで判定できます。

頂点 \(v_j\) についても同様に \(v_j\) から \(T\) に到達するパスが存在するかを調べればよく、これは \(G'\) を反転させることで同様に判定できます。

計算量は二部グラフの最大マッチングを求める計算量が律速となり、Dinic法を用いる場合は \(O(N \sqrt N)\) 、公式解説の手法を用いたマッチングならば \(O(N)\) となります。