Codeforces #360 Div1 A. NP-Hard Problem

毎度体調が悪い時の方がレートが上がるの謎。
http://codeforces.com/contest/687/problem/A

問題

無向グラフが与えられる。
共通部分を持たない２つの頂点集合A,Bのうち、それぞれが点カバーとなるものを構築せよ。

解法

２色に塗り分けるだけなので、適当にDFSしよう。

int N,M;
int C[202020];
vector<int> E[202020];
vector<int> R[2];

void paint(int cur,int col) {
	if(C[cur]!=-1) {
		if(C[cur]==col) return;
		_P("-1\n");
		exit(0);
	}
	C[cur]=col;
	R[col].push_back(cur+1);
	FORR(r,E[cur]) paint(r,col^1);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(C);
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) if(C[i]==-1) paint(i,0);
	
	FOR(i,2) {
		_P("%d\n",R[i].size());
		FOR(j,R[i].size()) _P("%d%s",R[i][j],(j==R[i].size()-1)?"\n":" ");
	}
	
	
}

まとめ

なんかやることに対して無駄に問題設定だけややこしくした感じ。