P4782 【模板】2-SAT 问题

1. 暴力判断做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;
const int MAXn = 1e6;
const int MAXm = 1e6;
const int MAXnd = MAXn * 2;
const int MAXeg = MAXm * 2;

template <typename T>
inline void read(T &a) {
    char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
    read(a), read(argv...);
}

int sta[MAXnd + 10];
int head[MAXnd + 10], cntnex, nex[MAXeg + 10], to[MAXeg + 10];
inline void Insert(int u, int v) {
    nex[++cntnex] = head[u];
    head[u] = cntnex;
    to[cntnex] = v;
}

int n, m;
int top, stk[MAXnd + 10];
inline int otherside(int cur) {
    if (cur > n) return cur - n;
    else return cur + n;
}
bool Dfs(int cur) {
    if (sta[cur] == 1) return 1;
    if (sta[cur] == -1) return 0;
    sta[cur] = 1; sta[otherside(cur)] = -1;
    stk[++top] = cur;
    for (int i = head[cur]; i; i = nex[i]) {
        if (!Dfs(to[i])) return 0;
    }
    return 1;
}

signed main() {
    read(n, m);
    for (int i = 1, a, opta, b, optb; i <= m; ++i) {
        read(a, opta, b, optb);
        Insert(opta ? a : a + n, optb ? b + n : b);
        Insert(optb ? b : b + n, opta ? a + n : a);
    }
    for (int i = 1; i <= n; ++i) {
        if (sta[i]) continue;
        top = 0;
        if (!Dfs(i)) {
            while (top) {
                sta[stk[top]] = sta[otherside(stk[top])] = 0;
                --top;
            }	
            if (!Dfs(i + n)) {
                puts("IMPOSSIBLE");
                return 0;
            }
        }
    }
    puts("POSSIBLE");
    for (int i = 1; i <= n; ++i) {
        printf("%d ", sta[i + n] == 1 ? 1 : 0);
    }
    puts("");
    return 0;
}

2. Tarjan 优化做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
const int MAXnd = MAXn * 2;
const int MAXeg = MAXm * 2;
int head[MAXnd + 10], cntnex, nex[MAXeg + 10], to[MAXeg + 10];
inline void Insert(int u, int v) {
    nex[++cntnex] = head[u];
    head[u] = cntnex;
    to[cntnex] = v;
}

int cntdfs, dfs[MAXnd + 10], low[MAXnd + 10];
int cntscc, inscc[MAXnd + 10]; vector<int> scc[MAXnd + 10];
int top, stk[MAXnd + 10]; bool instk[MAXnd + 10];
void Tarjan(int cur) {
    dfs[cur] = low[cur] = ++cntdfs;
    stk[++top] = cur; instk[cur] = 1;
    for (int i = head[cur]; i; i = nex[i]) {
        if (dfs[to[i]] == 0) {
            Tarjan(to[i]);
            low[cur] = min(low[cur], low[to[i]]);
        } else if (instk[to[i]]) {
            low[cur] = min(low[cur], dfs[to[i]]);
        }
    }
    if (dfs[cur] == low[cur]) {
        ++cntscc;
        int x;
        do {
            x = stk[top--]; instk[x] = 0;
            inscc[x] = cntscc;
            scc[cntscc].push_back(x);
        } while (x != cur);
    }
}

int n, m, N;
inline int otherside(int x) {
    if (x > n) return x - n;
    else return x + n;
}

bool chosescc[MAXnd + 10];
bool chosen[MAXn + 10];
signed main() {
    read(n, m);
    N = n * 2;
    for (int i = 1, x, a, y, b; i <= m; ++i) {
        read(x, a, y, b);
        Insert(a ? x : x + n, b ? y + n : y);
        Insert(b ? y : y + n, a ? x + n : x);
    }
    for (int i = 1; i <= N; ++i) {
        if (dfs[i] == 0) {
            Tarjan(i);
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (inscc[i] == inscc[n + i]) {
            puts("IMPOSSIBLE");
            return 0;
        }
    }
    puts("POSSIBLE");
    for (int i = 1; i <= cntscc; ++i) {
        if (chosescc[inscc[otherside(scc[i][0])]] == 0) {
            chosescc[i] = 1;
        }
    }
    for (int i = 1; i <= cntscc; ++i) {
        if (chosescc[i]) {
            for (auto j: scc[i]) {
                if (j > n) {
                    chosen[j - n] = 1;
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d ", chosen[i]);
    }
    puts("");
    return 0;
}