Codeforces Round #576 (Div. 1)C-Matching vs Independent Set
問題概要
3N頂点M辺の単純無向グラフがある。このグラフから次のどちらかを取り出したい。
・互いに辺で結ばれていないサイズNの頂点集合
・互いに頂点を共有していないサイズNの辺集合
解法
全ての辺を好きな順番で見ていき、これまでに辺集合に追加した辺と頂点を共有しないならその辺を辺集合に追加する。
全ての辺を見終わったときに辺集合のサイズがN以上ならばそれが答えで、N未満ならば、辺集合の辺の端点となっていない頂点N個が答えである。(どちらもサイズNまで小さくする必要がある場合がある)
これは余った頂点間に辺が存在するならば、辺集合に新たに辺を追加できることから、どちらもサイズ以外の条件は満たしているし、頂点の数が3Nなので少なくともどちらかはサイズの条件も満たしているのでうまくいく。
実際にACした提出