学步园

传送门：【HDU】1814 Peaceful Commission

题目分析：论文上的入门题竟然自己OJ上有！桑心，现在才发现。

这题就是求字典序最小解的2-sat。

i、j矛盾则建边< i , ~j > , < j , ~i >。

然后从小到大注意考虑没有赋值的变量 i，首先标记节点i<<1，并且沿着可行边（图中的有向边）标记所有能标记的节点。如果标记过程中发现某个变量对应的两个节点都被标记，则会引起矛盾，那么说明一开始的假设是错误的。回退到开头将所有过程中的标记清除，然后标记i<<1|1，按照上面的方法继续，如果无论标记i<<1或者i<<1|1都会引起矛盾，则整个2-sat无解。否则得到的所有赋值的节点构成的解正是字典序最小解。

代码如下：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )

const int MAXN = 16000 ;
const int MAXE = 40000 ;

struct Edge {
	int v ;
	Edge* next ;
} ;

Edge E[MAXE] , *H[MAXN] , *cur ;
int S[MAXN] , top ;
bool vis[MAXN] ;
int n , m ;

void init () {
	cur = E ;
	CLR ( H , 0 ) ;
	CLR ( vis , 0 ) ;
}

void addedge ( int u , int v ) {
	cur -> v = v ;
	cur -> next = H[u] ;
	H[u] = cur ++ ;
}

bool dfs ( int u ) {
	if ( vis[u ^ 1] ) return 0 ;
	if ( vis[u] ) return 1 ;
	vis[u] = 1 ;
	S[top ++] = u ;
	for ( Edge* e = H[u] ; e ; e = e -> next ) if ( !dfs ( e -> v ) ) return 0 ;
	return 1 ;
}

bool deal () {
	REP ( i , 0 , n << 1 ) {
		if ( !vis[i] && !vis[i ^ 1] ) {
			top = 0 ;
			if ( !dfs ( i ) ) {
				while ( top ) vis[S[-- top]] = 0 ;
				if ( !dfs ( i ^ 1 ) ) return 0 ;
			}
		}
		++ i ;
	}
	return 1 ;
}

void scanf ( int& x , char c = 0 ) {
	while ( ( c = getchar () ) < '0' || c > '9' ) ;
	x = c - '0' ;
	while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ;
}

void solve () {
	int u , v ;
	init () ;
	while ( m -- ) {
		scanf ( u ) , scanf ( v ) ;
		-- u , -- v ;
		addedge ( u , v ^ 1 ) ;
		addedge ( v , u ^ 1 ) ;
	}
	if ( deal () ) {
		REP ( i , 0 , n << 1 ) if ( vis[i] ) printf ( "%d\n" , i + 1 ) ;
	} else printf ( "NIE\n" ) ;
}

int main () {
	while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ;
	return 0 ;
}