[問題案] Maximum Independent Set in a Bipartite Graph（+ Minimum Vertex Cover, Minimum Edge Cover）

[drken1215]

Problem name: Maximum Independent Set in a Bipartite Graph

問題文

頂点数が $L, R$、辺数が $M$ の二部グラフが与えられる。 $i$ 番目の辺は $(a_i, b_i)$ である。

この二部グラフの最大独立集合を求めてください。

制約

• $1 \le L, R \le 10^5$
• $1 \le M \le 2 \times 10^5$
• $0 \le a_i \lt L$
• $0 \le b_i \lt R$
• 多重辺は存在しない

入力

$L$ $R$
$a_{0}$ $b_{0}$
$a_1$ $b_1$
$\dots$
$a_{M-1}$ $b_{M-1}$

出力

$K$
$v_{0}$ $v_{1}$ $\dots$ $v_{K-1}$

• $K$ は最大独立集合のサイズ
• $v_{0}$ $v_{1}$ $\dots$ $v_{K-1}$ は最大独立集合をなす $K$ 個の頂点

(Optional) Note / Discussion

• "Matching on Bipartite Graph" があれば十分かもしれないのですが、最大独立集合を復元する部分もライブラリ化してしまいたい気持ちになりました
  • 最小点被覆、最小辺被覆も同様
• Library Checker 上に意外とまだないことに気づき、提案してみました
• "Matching on Bipartite Graph" に問題文・制約を合わせてみました
  • なお、"Matching on Bipartite Graph"（ https://judge.yosupo.jp/problem/bipartitematching ）の問題文で、一部タイポらしきものを見つけました。「辺数 が M」と書きたかったと思われる部分が「辺が M」になっています

[NachiaVivias]

なお、"Matching on Bipartite Graph"（ https://judge.yosupo.jp/problem/bipartitematching ）の問題文で、一部タイポらしきものを見つけました。「辺数 が M」と書きたかったと思われる部分が「辺が M」になっています

pull request を作って頂けると、すぐにマージして修正できますが、いかがでしょうか。

[drken1215]

ありがとうございます。
1 文字加えるだけの変更で恐縮ですが、Pull Request を作ってみました。
#1394

[maspypy]

最大マッチング、最小頂点被覆、最小辺被覆、最大独立集合
と全部置く意味があるとはあまり思わないですが、

最小辺被覆：最大マッチングとほぼ同じ出力
最小頂点被覆：最大独立集合とほぼ同じ出力

で、最大マッチングと最大独立集合の 2 つ用意というくらいはまあ入れても大丈夫かなと思っています。