4005번: 테이블 색칠하기

https://www.acmicpc.net/problem/4005

#include<cstdio>
#include<vector>
#define mod int(1e9)
using namespace std;
const int MX = 1e5;
int n, m, k, r = 1, vis[MX + 1], c[MX + 1], ck[MX + 1], tcnt, ccnt;
vector<pair<int, int> > row[MX + 1];
vector<int> col[MX + 1];
void f(int h) {
    if (vis[h]) return;
    vis[h] = 1;
    int cnt = 0, tot = 0;
    for (auto it : row[h]) if (ck[it.first]) {
        tot++;
        int ans = it.second ^ (h&it.first & 1);
        if (c[it.first] ^ ans) cnt++;
    }
    if (0 < cnt && cnt < tot) r = 0;
    for (auto it : row[h]) if (!ck[it.first]) {
        tcnt++;
        ck[it.first] = 1;
        c[it.first] = it.second^cnt > 0 ^ (h&it.first & 1);
    }
    for (auto it : row[h]) if (ck[it.first] == 1) {
        ck[it.first]++;
        for (int t : col[it.first]) f(t);
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    while (k--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        row[a].push_back({ b,c });
        col[b].push_back(a);
    }
    ccnt = m - 1;
    for (int i = 1; i <= n; i++) {
        tcnt = 0;
        f(i);
        if (tcnt) ccnt -= tcnt - 1;
    }
    while (ccnt--) r = (r * 2) % mod;
    for (int i = 1; i <= n; i++) if (row[i].empty()) r = (r * 2) % mod;
    printf("%d", r);
    return 0;
}

11278번: 2-SAT - 2

https://www.acmicpc.net/problem/11278

#include<stdio.h>
int n, m, a[100], b[100];
int f(int x, int y) {
    return x < 0 ? 1 - (y >> -x - 1) % 2 : (y >> x - 1) % 2;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++)
        scanf("%d %d", &a[i], &b[i]);
    int res = -1;
    for (int i = 0; i < 1 << n; i++) {
        bool flag = true;
        for (int j = 0; j < m; j++)
            flag &= f(a[j], i) | f(b[j], i);
        if (flag) {
            res = i;
            break;
        }
    }
    if (res == -1) puts("0");
    else {
        puts("1");
        for (int i = 0; i < n; i++)
            printf("%d ", (res >> i) % 2);
    }
    return 0;
}

11280번: 2-SAT - 3

https://www.acmicpc.net/problem/11280

#include<stdio.h>
#include<vector>
#define pb(x) push_back(x);
using namespace std;
const int MAX_N = 10000;
int n, m, c[MAX_N * 2 + 1];
vector<int> adj[2][MAX_N * 2 + 1];
bool ck[MAX_N * 2 + 1];
vector<int> vis, tvis;
void dfs(int h, bool type) {
    if (ck[h] != type) return;
    ck[h] = !type;
    for (auto t : adj[type][h])
        dfs(t, type);
    vis.pb(h);
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[0][n - a].pb(n + b);
        adj[0][n - b].pb(n + a);
        adj[1][n + b].pb(n - a);
        adj[1][n + a].pb(n - b);
    }
    for (int i = 0; i < n; i++)
        dfs(i, false), dfs(i + n + 1, false);
    tvis = vis;
    for (int i = tvis.size() - 1; i >= 0; i--) {
        if (!ck[tvis[i]]) continue;
        vis.clear();
        dfs(tvis[i], true);
        for (auto it : vis) c[it] = i;
    }
    bool res = true;
    for (int i = 0; i < n; i++)
        res &= c[i] != c[2 * n - i];
    printf("%d", res);
    return 0;
}

11281번: 2-SAT - 4

https://www.acmicpc.net/problem/11281

#include<stdio.h>
#include<vector>
#define pb(x) push_back(x);
using namespace std;
const int MAX_N = 10000;
int n, m, c[MAX_N * 2 + 1];
bool ck[MAX_N * 2 + 1];
vector<int> vis, tvis, adj[2][MAX_N * 2 + 1];
void dfs(int h, bool type) {
    if (ck[h] != type) return;
    ck[h] = !type;
    for (auto t : adj[type][h])
        dfs(t, type);
    vis.pb(h);
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[0][n - a].pb(n + b);
        adj[0][n - b].pb(n + a);
        adj[1][n + b].pb(n - a);
        adj[1][n + a].pb(n - b);
    }
    for (int i = 0; i < n; i++)
        dfs(i, false), dfs(i + n + 1, false);
    tvis = vis;
    for (int i = tvis.size() - 1; i >= 0; i--) {
        if (!ck[tvis[i]]) continue;
        vis.clear();
        dfs(tvis[i], true);
        for (auto it : vis) c[it] = i;
    }
    bool res = true;
    for (int i = 0; i < n; i++)
        res &= c[i] != c[2 * n - i];
    printf("%d\n", res);
    if (res)
        for (int i = n + 1; i <= 2 * n; i++)
            printf("%d ", c[i] < c[2 * n - i]);
    return 0;
}

11277번: 2-SAT - 1

https://www.acmicpc.net/problem/11277

#include<stdio.h>
int n, m, a[100], b[100];
int f(int x, int y) {
    return x < 0 ? 1 - (y >> -x - 1) % 2 : (y >> x - 1) % 2;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++)
        scanf("%d %d", &a[i], &b[i]);
    bool res = false;
    for (int i = 0; i < 1 << n; i++) {
        bool flag = true;
        for (int j = 0; j < m; j++)
            flag &= f(a[j], i) | f(b[j], i);
        res |= flag;
    }
    printf("%d", res);
    return 0;
}