『算法-ACM 竞赛-图论』2-SAT-暴力染色法求字典序最小模版

图论–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\n", i+1);
        }
        else
        printf("NIE\n");
    }
}