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

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

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define MAX 17000

int n,m;
vector< vector<int> > path;
vector< vector<int> > dag;
char color[MAX];
bool ans;
vector< int > ans_seq;
queue< int > SQ;
queue< int > SQ2;

int scc, step;
int id[MAX];
int order[MAX], order_pos, order2[MAX], order2_pos;
int vis[MAX];
int in_degre[MAX];

void dfs(int pos)
{
    int i,j,next,l,pre;
	
    vis[pos] = step ++;
    order[ order_pos ++ ] = pos;
    order2[ order2_pos ++ ] = pos;
    l = path[pos].size();
    for (i=0;i<l;i++) {
        next = path[pos][i];
        if (vis[next] == 0) {
            dfs(next);
        }
        else if (id[next] == 0) {//have a circle and belong to nothing
            while (vis[ order2[order2_pos -1] ] > vis[next]) {//back to begin of circle
                order2_pos --;
            }
        }
    }//for i
    if (order2[order2_pos -1] == pos) {//if pos back to begin of scc
        order2_pos --;
    }
    else {
        return ;
    }
    do {//record scc
        pre = order[order_pos -1];
        id[pre] = scc;
        order_pos --;
    } while(pre != pos);
    scc ++;
}

void topological_sort()
{
	int i,j,ps,now,next;
	
	while (!SQ.empty()) {
		now = SQ.front();
		SQ.pop();
		if (color[now] != 0) {//choose a scc without colored
			continue ;
		}
		color[now] = 'R';//color it
		in_degre[now] = -1;
		for (i=1;i<=2*n;i++) {//delete against scc
			if (id[i] == now) {
				int ag_pos;
				if (i % 2 == 0) {
					ag_pos = i-1;
				}
				else {
					ag_pos = i+1;
				}
				int ag_id = id[ag_pos];
				
				while (!SQ2.empty()) {
					SQ2.pop();
				}
				SQ2.push(ag_id);
				while (!SQ2.empty()) {//delete his son
					ag_id = SQ2.front();
					SQ2.pop();
					if (color[ag_id] == 'B') {
						continue ;
					}
					color[ag_id] = 'B';
					int ps = dag[ag_id].size();
					for (j=0;j<ps;j++) {
						next = dag[ag_id][j];
						SQ2.push(next);
					}
				}//while SQ2
			}
		}//end of delete
		//find next scc
		ps = dag[now].size();
		for (i=0;i<ps;i++) {
			next = dag[now][i];
			in_degre[next] --;
			if (in_degre[next] == 0) {
				SQ.push(next);
			}
		}
	}//while SQ
}

//check 2-sat, false mean no solution
bool Gabow()
{
    int i,j,l;
    //dfs in original graph
    memset(id, 0, sizeof(id));
    memset(vis, 0, sizeof(vis));
    scc = 1;
	step = 1;
	order[0] = order2[0] = INT_MIN;
    order_pos = order2_pos = 1;
    for (i=1; i<=2*n ;i++) {
        if (vis[i] == 0) {
            dfs(i);
        }
    }

    //statist
	for (i=1;i<=n;i++) {
		if (id[i*2-1] == id[i*2]) {
			return false;
		}
	}
	scc --;
	return true;
}

void print()
{
	int i,j;
	ans_seq.clear();
	for (i=1; ans && i<=n ;i++) {//O(V)
		if ( color[ id[i*2 -1] ] == 'R') {
			ans_seq.push_back(i*2 -1);
		}
		else {
			ans_seq.push_back(i*2);
		}
	}//for i
	if (!ans) {
		puts("NIE");
		return ;
	}
	j = ans_seq.size();
	for (i=0;i<j;i++) {
		printf("%d\n",ans_seq[i]);
	}
}

int main()
{
	int i,j,l;
	
	while (scanf("%d %d",&n,&m)==2) {
		path.resize(2*n+10);
		for (i=2*n+4;i>=0;i--) {
			path[i].clear();
		}
		//set up graph and inverse 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);
		}
		
		ans = Gabow();
		if (ans) {
			dag.resize(scc +10);
			for (i=0;i<scc+10;i++) {
				dag[i].clear();
			}
			//set scc dag
			memset(in_degre,0,sizeof(in_degre));//prepare for top-sort
			for (i=1;i<=2*n;i++) {//O(E)
				l = path[i].size();
				int id1 = id[i];
				for (j=0;j<l;j++) {
					int id2 = id[ path[i][j] ];
					if (id1 != id2) {//id1 -> id2
						dag[id2].push_back(id1);//inverse path id2 -> id1
						in_degre[id1] ++;
					}
				}
			}//for i
			//toplogy sort
			l = SQ.size();
			while (l --) {
				SQ.pop();
			}
			for (i=1;i<=scc;i++) {
				if (in_degre[i] == 0) {
					SQ.push(i);//begin to top-sort
				}
			}
			//selecte and delete, color it
			memset(color,0,sizeof(color));
			topological_sort();
		}//if ans
		print();
	}
}