2-SAT,输出字典序最小的解,白书模板。
//TwoSAT输出字典序最小的解的模板
//注意:0,1是一组,1,2是一组..... #include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std; const int maxn=+;
int m; struct TwoSAT
{
int n;
vector<int> G[maxn*];
bool mark[maxn*];
int S[maxn*],c; bool dfs(int x)
{
if(mark[x^]) return false;
if(mark[x]) return true;
mark[x]=true;
S[c++]=x;
for(int i=;i<G[x].size();i++)
if(!dfs(G[x][i])) return false;
return true;
} void init(int n)
{
this->n=n;
for(int i=;i<n*;i++) G[i].clear();
memset(mark,,sizeof mark);
} void add_clause(int x,int y)
{
G[x].push_back(y^);
G[y].push_back(x^);
} bool solve()
{
for(int i=;i<*n;i+=)
if(!mark[i]&&!mark[i+])
{
c=;
if(!dfs(i))
{
while(c>) mark[S[--c]]=false;
if(!dfs(i+)) return false;
}
}
return true;
} //输出字典序最小的解
void Printf()
{
for(int i=;i<n;i++)
{
if(mark[*i]) printf("%d\n",*i+);
else printf("%d\n",*i++);
}
}
}; int main()
{
TwoSAT T;
while(~scanf("%d%d",&T.n,&m))
{
T.init(T.n);
for(int i=;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
a--;b--;
T.add_clause(a,b);
}
if(T.solve()) T.Printf();
else printf("NIE\n");
}
return ;
}