hit1917 peaceful commission(2-sat,o(nm)).cpp

杭电acm解题报告2001---2099.

//O(NM)
//枚举每一对尚未确定的Ai, Ai' ，任选1个，推导出相关的组，若不矛盾，则可选择；
//否则选另1个，同样推导。若矛盾，问题必定无解。
//由于Ai,Ai' 都是尚未确定的，它们不与之前的组相关联，前面的选择不会影响Ai, Ai' 。
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 17000

int n,m;
vector< vector<int> > path;
bool sel[MAX];
bool ans;
vector< int > ans_seq;
vector< int > stack;

bool dfs(int pos)
{
	int i,j,l;

	sel[pos] = true;
	stack.push_back(pos);
	l = path[pos].size();
	for (i=0;i<l;i++) {
		j = path[pos][i];//must be selection
		if (sel[j]) {//be selected
			continue ;
		}
		int j2;
		if (j%2 == 1) {
			j2 = j+1;
		}
		else {
			j2 = j-1;
		}
		if ( sel[j2] || !dfs(j) ) {//can't select j
			sel[pos] = false;
			return false;
		}
	}
	return true;
}

void print()
{
	int i,j;
	ans_seq.clear();
	for (i=1;i<=2*n;i+=2) {
		if (sel[i]) {
			ans_seq.push_back(i);
		}
		else {
			ans_seq.push_back(i+1);
		}
	}//for i
	j = ans_seq.size();
	for (i=0;i<j;i++) {
		printf("%d\n",ans_seq[i]);
	}
	//printf("=========\n");
}

int main()
{
	int i,j;
	while (scanf("%d %d",&n,&m)==2) {
		path.resize(2*n+10);
		for (i=2*n+4;i>=0;i--) {
			path[i].clear();
			sel[i] = false;
		}
		//set up graph
		for (i=0;i<m;i++) {
			int x,y,tx,ty;
			scanf("%d %d",&x,&y);
			if (x % 2 == 0) {
				tx = x-1;
			}
			else {
				tx = x+1;
			}
			if (y % 2 == 0) {
				ty = y-1;
			}
			else {
				ty = y+1;
			}
			path[x].push_back(ty);
			path[y].push_back(tx);
		}
		/*
		printf("---------\n");
		for (i=1;i<=2*n;i++) {
			printf("%d:",i);
			for (j=0;j<path[i].size();j++) {
				printf(" %d",path[i][j]);
			}
			printf("\n");
		}
		printf("---------\n");
		*/
		ans = true;
		stack.resize(2*n+10);
		for (i=1;i<=2*n;i+=2) {
			if (!sel[i] && !sel[i+1]) {//if a group not be selection
				stack.clear();//record points that i-pos can reached
				if ( !dfs(i) ) {
					for (j=stack.size()-1;j>=0;j--) {//if i-pos failed, recover
						sel[ stack[j] ] = false;
					}
					if ( !dfs(i+1) ) {
						ans = false;
						break ;
					}
				}
				//print();
			}
		}//for i
		for (i=1;ans && i<=2*n;i+=2) {
			if (sel[i] == sel[i+1]) {//a group have conflict
				ans = false;
			}
		}
		if (!ans) {
			puts("NIE");
		}
		else {
			print();
		}
	}
}