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