NP-Hard Problem [Codeforces 360 : Div1 A, Div2 C]

問題

http://codeforces.com/contest/688/problem/C

頂点n,辺mの無向グラフGが与えられる。
この時、以下の条件を満たす頂点の部分集合A,Bを答えよ。
もし、なければ「-1」を出力。

• AとBは独立である(要素が被らない)
• AもBも元々のグラフGの頂点被覆である

頂点被覆とはグラフの全ての辺に対して、どちらかの頂点が含まれている頂点集合です。
Subset A of its vertices is called a vertex cover of this graph, if for each edge uv there is at least one endpoint of it in this set, i.e. u ∈ A or v ∈ A (or both)

2 <= n <= 10^5
1 <= m <= 10^5

思考の流れ

1. 「頂点被覆」でググると「頂点被覆は二部マッチングと同じだぞ」とか出る
2. なので二部マッチング問題として特とすぐできる（みたいです）

二部マッチング問題解けない人（私）向け

3. 制限を見るとO(n)かO(nlogn)でしか解けない雰囲気
4. コドフォのDiv2のCのグラフでよく見るイメージなのが「DFS・BFS」
5. 頂点を2つに分けるので彩色問題っぽい

ここからちょっと飛躍（考察）

6. AもBも頂点被覆になるためには「各辺の端点は片方がA,もう片方がBに属していないといけない」
7. ということは、辺によって繋がれている2頂点は異なる集合の要素同士になる
8. 2色で順番に塗っていけばいいかな？

BFSを使って塗っていきます coloring()
　1. 全ての頂点の色を-1とする
　2. 全頂点に対して順番に、その頂点の色が-1なら（塗られてないなら）そこからBFSで0,1,0,1,...と頂点に色をつけていく

9. 最後に全ての辺に対して、異なる色で塗られているか確認 -> 塗られている「Yes」ダメ「No」

解法

http://codeforces.com/contest/688/submission/18816391
入力・出力数が多いのでscanf,printfなどを使うように工夫しないとTLEするかも

int n, m;
int u[101010], v[101010];
vector<int> E[101010];
//-----------------------------------------------------------------
int c[101010];
void coloring()
{
	rep(i, 0, n) c[i] = -1;
	rep(i, 0, n) if (c[i] < 0) {
		if (E[i].size() == 0) continue;

		queue<int> que;
		que.push(i);
		c[i] = 0;

		while (!que.empty()) {
			int j = que.front(); que.pop();

			for (int k : E[j]) if (c[k] < 0) {
				c[k] = (c[j] + 1) % 2;
				que.push(k);
			}
		}
	}
}
//-----------------------------------------------------------------
int main() {
	scanf("%d %d", &n, &m);
	rep(i, 0, m) {
		scanf("%d %d", &u[i], &v[i]);
		u[i]--; v[i]--;
		E[u[i]].push_back(v[i]);
		E[v[i]].push_back(u[i]);
	}

	coloring();

	rep(i, 0, m) if (c[u[i]] == c[v[i]]) {
		printf("-1\n");
		return 0;
	}

	vector<int> ans[2];
	rep(i, 0, n) if (0 <= c[i]) ans[c[i]].push_back(i);

	rep(i, 0, 2) {
		printf("%d\n", ans[i].size());
		for (int j : ans[i]) printf("%d ", j + 1);
		printf("\n");
	}
}