1.2-sat

主要是化简问题，转化成(a1||b1)&&(a2||b2)&&...&&(an||bn)=1，求每个元素的真值。

每个元素真值为真/假抽象成一对点，然后每对里面只能选恰好一个点。除此之外把(ai||bi)==1转化成!ai->bi&&!bi->ai，然后整个图里面A->B的意思就是A选了B就必须选。缩点(同一个强连通分量中的点一定决策一样)之后变成DAG图(同时拿到拓扑序)，只要没有成对的点在一个强连通分量里面就存在解；给出一组解的话就是选拓扑序小的那个点。

#include<bits/stdc++.h>

#define maxn 2000010
using namespace std;
int n, m, dfn[maxn], low[maxn], bl[maxn], topt, sum, s[maxn], top, f[maxn];
vector<int> G[maxn];

void Dfs(int u) {
    dfn[u] = low[u] = ++topt;
    s[++top] = u, f[u] = 1;
    for (int v:G[u]) {
        if (dfn[v] == 0) {
            Dfs(v), low[u] = min(low[u], low[v]);
        } else if (f[v])low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        sum++;
        while (s[top] != u) {
            f[s[top]] = 0, bl[s[top]] = sum, top--;
        }
        f[s[top]] = 0, bl[s[top]] = sum, top--;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    int a, va, b, vb;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d%d", &a, &va, &b, &vb);
        G[a + n * (va & 1)].push_back(b + n * (vb ^ 1));
        G[b + n * (vb & 1)].push_back(a + n * (va ^ 1));
    }
    for (int i = 1; i <= n * 2; i++)
        if (!dfn[i])Dfs(i);
    for (int i = 1; i <= n*2; i++)printf("%d ", bl[i]);
    printf("\n");
    int ok = 1;
    for (int i = 1; i <= n; i++)
        if (bl[i] == bl[i + n])ok = 0;
    if (ok == 0)printf("IMPOSSIBLE\n");
    else {
        printf("POSSIBLE\n");
        for (int i = 1; i <= n; i++)
            if (bl[i] < bl[i + n])printf("1 ");
            else printf("0 ");
        printf("\n");
    }
    return 0;
}