《P4782 【模板】2-SAT 问题》

2 - sat问题：

就是一些元素，他们的值只能为布尔值0,1.

给出一些限制关系，并且每对关系都是两个数之间的。

让你找出一组构造，让所有关系都满足。

解法：

首先要建图：

我们规定，a为1的点为a + n，a为0的点为a。

那么对于给定的一对关系a , b。

如果是a == 1，b == 1，那么说明a | b。

利用可以转化为!a ->b，!b -> a。

然后我们连边，即!a 到 b一条,!b 到 a一条。

若a == 0,b == 0 ： !a | !b：

a -> !b，b -> !a。

其余情况都同理转化连边即可。

然后我们tarjan对强连通分量去染色：

对于无解的情况：如果存在一组i 与 i+n在同一个强连通分量中，那么就是无解。

否则就有解：那么此时它的值为col[i] > col[i + n]的布尔值。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e6 + 5;
const int M = 5e6 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
}
using namespace FASTIO;

int n,m,col[N << 1],dfn[N << 1],low[N << 1],tim = 0,clr = 0;
vector<int> G[N << 1];
stack<int> S;
bool vis[N << 1];
void tarjan(int u){ 
    S.push(u);
    vis[u] = 1;
    low[u] = dfn[u] = ++tim;
    for(auto v : G[u]){
        if(dfn[v] == 0){
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(vis[v] == 1) low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u]){
        clr++;
        while(S.top() != u){
            col[S.top()] = clr;
            vis[S.top()] = 0;
            S.pop();
        }
        col[S.top()] = clr;
        vis[S.top()] = 0;
        S.pop();
    }
}
int main()
{
    n = read(),m = read();
    while(m--){
        int i,a,j,b;i = read(),a = read(),j = read(),b = read();
        if(a == 0 && b == 0){//!a | !b,  a -> !b , b -> !a
            G[i + n].push_back(j);
            G[j + n].push_back(i);
        }
        else if(a == 1 && b == 1){//a | b , !a -> b,!b -> a
            G[i].push_back(j + n);
            G[j].push_back(i + n);
        }
        else if(a == 1 && b == 0){//a | !b, !a -> !b,b -> a
            G[i].push_back(j);
            G[j + n].push_back(i + n);
        }
        else{//!a | b,a -> b , !b -> !a 
            G[i + n].push_back(j + n);
            G[j].push_back(i);
        }
    }
    for(int i = 1;i <= 2 * n;++i) if(!dfn[i]) tarjan(i);//找环,注意是两倍点
    for(int i = 1;i <= n;++i){
        if(col[i] == col[i + n]) {// a 与 !a在同一强连通分量内，无解
            printf("IMPOSSIBLE
");
            return 0;
        }
    }
    printf("POSSIBLE
");
    for(int i = 1;i <= n;++i) {//根据拓扑的强连通分量的顺序确定构造的值,a < !a = 1,else = 0
        printf("%d%c",col[i] > col[i + n] ? 1 : 0,i == n ? '
' : ' ');
    }
      system("pause");
    return 0;
}