Codeforces 688C NP-Hard Problem【二分图】【搜索】

题目链接：http://codeforces.com/contest/688/problem/C

题意：

有一个 n 个点 m 条边，如果认为两个点是在一个集合，则这两个点没有边连接。求这个图能否能将所有的点都存到两个集合中去，能输出两个集合的点，不能输出 -1。

题解：

直接深搜，用到二分图染色的知识。水过去！

代码：

#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

const int size = 1e5+5;
int n, m;
vector<int> edges[size];
int vis[size], mark, cr[size];

void dfs(int id, int color) {			// 对第 id 个点进行搜索，遍历所有与它相连的节点并染色，color表示这个点以及所有与它相连的节点的颜色
	vis[id] = 1;
	cr[id] = color;

	for ( int i = 0; i < edges[id].size(); i ++ ) {
		if(!vis[edges[id][i]]) {
			dfs(edges[id][i], color ^ 1);
		} else if(cr[edges[id][i]] == color) {
			mark = 0;
			return ;
		}
	}

	return ;
}

int main() {
	// freopen("688C.in","r",stdin);
	memset(vis, 0, sizeof(vis));
	memset(cr, -1, sizeof(cr));

	scanf("%d %d", &n, &m);
	for ( int i = 1; i <= m; i ++ ) {
		int x, y;
		scanf("%d %d", &x, &y);
		edges[x].push_back(y); edges[y].push_back(x);
	}

	mark = 1;
	for ( int i = 1; i <= n; i ++ ) {
		if(cr[i] == -1) dfs(i, 1);
		if( !mark ) { puts("-1"); return 0; }		// 不符合要求
	}

	int cnt0 = 0, cnt1 = 0;
	for ( int i = 1; i <= n; i ++ ) {
		if(cr[i] == 1) cnt1 ++;
		else if(cr[i] == 0) cnt0 ++;
	}
	printf("%d\n", cnt0);
	for ( int i = 1; i <= n; i ++ ) if(cr[i] == 0) printf("%d ", i);
	printf("\n%d\n", cnt1);
	for ( int i = 1; i <= n; i ++ ) if(cr[i] == 1) printf("%d ", i);

	return 0;
}