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;
}