图论--2-SAT--暴力染色法求字典序最小模版

#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define MAXN 40000+10
#define MAXM 200000+10
#define INF 1000000
using namespace std;
struct Edge
{
	int from, to, next;
}edge[MAXM];
int head[MAXN], edgenum;
stack<int> S;
bool mark[MAXN];//标记是否为真 
int N, M;
void init()
{
	edgenum = 0;
	memset(head, -1, sizeof(head));
	memset(mark, false, sizeof(mark));
} 
void addEdge(int u, int v)
{
	Edge E = {u, v, head[u]};
	edge[edgenum] = E;
	head[u] = edgenum++; 
}
void getMap()
{
	int a, b;
	while(M--)
	{
		scanf("%d%d", &a, &b);
		a--, b--;
		addEdge(a, b ^ 1);
		addEdge(b, a ^ 1);
	}
}
bool dfs(int u)
{
	if(mark[u ^ 1]) return false;
	if(mark[u]) return true;
	mark[u] = true;
	S.push(u);
	for(int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].to;
		if(!dfs(v)) return false;
	}
	return true;
}
bool solve()
{
	for(int i = 0; i < 2*N; i+=2)//共N组 
	{
		if(!mark[i] && !mark[i ^ 1])//还没有判定 
		{
			while(!S.empty())//用STL的话 注意清空栈 
			{
				S.pop();
			}
			if(!dfs(i))
			{
				while(!S.empty())
				{
					int v = S.top();
					S.pop();
					mark[v] = false;
				}
				if(!dfs(i ^ 1))//矛盾 必无解 
				return false;
			}
		}
	}
	return true;
}
int main()
{
	while(scanf("%d%d", &N, &M) != EOF)
	{
		init();
		getMap();
		if(solve())
		{
			for(int i = 0; i < 2*N; i++)
			if(mark[i]) printf("%d
", i+1);
		}
		else
		printf("NIE
");
	}
}