洛谷题单指南-连通性问题-P4782 【模板】2-SAT

原题链接：https://www.luogu.com.cn/problem/P4782

题意解读：2-SAT模版题。

解题思路：

1、定义

2 - SAT问题是给定一个布尔公式，该公式由若干个子句组成，每个子句都是两个文字的析取（或关系），例如(a ∨ b)、(¬c ∨ d)等，其中a、b、c、d是布尔变量，¬表示取反。问题的目标是判断是否存在一种变量赋值方式，使得整个布尔公式为真。

2、算法思路

建立蕴含图：对于每个子句(a ∨ b)，可以将其转化为两个蕴含关系¬a->b和¬b->a。然后，将每个变量x及其否定¬x看作图中的节点，将蕴含关系看作有向边，这样就可以得到一个蕴含图。对于节点x，其否定的节点可以设为x+n。

强连通分量分解：使用 Tarjan 算法等对蕴含图进行强连通分量分解。如果一个变量x和它的否定¬x在同一个强连通分量中，那么显然无法找到一种赋值使得整个公式成立，因为这意味着x既必须为真又必须为假，产生矛盾。编程时，枚举所有变量i，如果i和i+n的scc编号相同，说明产生矛盾。

拓扑排序与赋值：如果x和¬x不在同一个强连通分量中，那么可以对强连通分量进行拓扑排序。按照拓扑序的逆序进行赋值，对于每个强连通分量，如果其中的变量尚未赋值，则将该强连通分量中的所有变量赋值为真，同时将其对应的否定变量赋值为假。这样的赋值方式可以保证满足所有的子句。编程实现时，直接枚举所有的变量i，看i和i+n谁的拓扑序更大（也就是谁的scc编号更小），如果i拓扑序小i变量为true，如果i+n拓扑序小i变量为false。

3、时间复杂度

构建蕴含图的时间复杂度为O(m)，其中m是子句的数量。Tarjan 算法求强连通分量的时间复杂度为O(n + m)，其中n是变量的数量。所以整体时间复杂度为O(n + m)。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 2000005, M = 2000005;

int head[N], to[M], nxt[M], idx;
int dfn[N], low[N], timestamp;
stack<int> stk;
bool vis[N];
int scc[N], cnt;
bool ans[N];
int n, m;

void add(int a, int b)
{
    to[++idx] = b;
    nxt[idx] = head[a];
    head[a] = idx;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    vis[u] = true;
    for(int i = head[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v])
        {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u])
    {
        cnt++;
        while(true)
        {
            int t = stk.top(); stk.pop();
            scc[t] = cnt;
            vis[t] = false;
            if(t == u) break;
        }
    }
}

bool check()
{
    for(int i = 1; i <= n * 2; i++) //注意节点总数是2n
        if(!dfn[i])
            tarjan(i);

    for(int i = 1; i <= n; i++)
        if(scc[i] == scc[i + n]) //i和非i在同一个强联通分量
            return false;

    return true;
}

int main()
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1;i <= m; i++)
    {
        int x, a, y, b;
        cin >> x >> a >> y >> b;
        if(a == 1 && b == 1) // x || y
        {
            add(x + n, y); // !x -> y
            add(y + n, x); // !y -> x
        }
        else if(a == 1 && b == 0) // x || !y
        {
            add(x + n, y + n); // !x -> !y
            add(y, x); // y -> x
        }
        else if(a == 0 && b == 1) // !x || y
        {
            add(x, y); // x -> y
            add(y + n, x + n); // !y -> !x
        }
        else // !x || !y
        {
            add(x, y + n); // x -> !y
            add(y, x + n); // y -> !x
        }
    }

    if(!check()) cout << "IMPOSSIBLE" << endl;
    else 
    {
        cout << "POSSIBLE" << endl;
        for(int i = 1; i <= n; i++) 
            cout << (scc[i] < scc[i + n]) << " ";  //i比非i的拓扑序靠前则是1，否则是0
    }

    return 0;
}