[백준 11281] 2-SAT - 4

문제

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

 

알고리즘

2-SAT

 

풀이

이 문제에서 실제 해까지 찾아서 출력하는 문제입니다. SCC 이후 하나의 간선을 구성하는 두 정점을 살펴봅시다. 앞서 살펴본 바와 같이 u->v를 만족하기 위해선 not u 일 땐 v가 무엇이 와도 상관이 없으나 True u 일 땐 2-CNF에서의 절을 만족하기 위해 v가 True임이 강제됩니다. 즉 우리는 위상 정렬상 빠른 쪽에 위치한 정점을 False로 평가하는 것이 True로 평가하는 것에 비해 항상 이득임을 알 수 있습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

#define t(x) (x<<1)
#define f(x) (x<<1|1)
#define W(x) (x>0?t(x-1):f(-(x+1)))

int N, M, u, v, VC, SC;

vector<vector<int>> adj;
vector<int> discovered, sccid;
stack<int> st;
void OR(int u, int v) {
    adj[W(u) ^ 1].emplace_back(W(v));
    adj[W(v) ^ 1].emplace_back(W(u));
}

int scc(int here) {
    int ret = discovered[here] = VC++;
    st.emplace(here);
    for (auto there : adj[here]) {
        if (discovered[there] == -1) ret = min(ret, scc(there));
        else if (sccid[there] == -1) ret = min(ret, discovered[there]);
    }

    if (ret == discovered[here]) {
        while (1) {
            int t = st.top();
            st.pop();
            sccid[t] = SC;
            if (t == here) break;
        }
        ++SC;
    }
    return ret;
}

int main() {
    FAST;

    cin >> N >> M;
    adj.resize(N << 1);
    rep(i, M) {
        cin >> u >> v;
        OR(u, v);
    }
    discovered = sccid = vector<int>(N << 1, -1);
    rep(i, N << 1) if (discovered[i] == -1) scc(i);
    bool flag = 1;
    rep(i, N) if (sccid[t(i)] == sccid[f(i)]) {
        flag = 0;
        break;
    }
    cout << flag << '\n';
    if (flag) {
        rep(i, N) {
            if (sccid[t(i)] < sccid[f(i)]) cout << 1 << ' ';
            else cout << 0 << ' ';
        }
    }
    return 0;
}