BOJ 11281 2-SAT - 4

1 개요

BOJ 11281 2-SAT - 4

• 백준 온라인 저지 11281번 문제
• BOJ 44단계

2 같이 보기

• BOJ 11277 2-SAT - 1
• BOJ 11278 2-SAT - 2
• BOJ 11280 2-SAT - 3
• BOJ 11281 2-SAT - 4

3 C++

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

int N, M;
vector<int> lines[20001];
stack<int> st;
int visits[20001], n_visit;
int roots[20001], n_root;

int SCC(int cur) {
    int res = visits[cur] = ++n_visit;
    st.push(cur);
    for (int l : lines[cur]) {
        if (!roots[l]) {
            res = min(res, visits[l] ? visits[l] : SCC(l));
        }
    }
    if (res == visits[cur]) {
        n_root++;
        while (!st.empty()) {
            int tmp = st.top(); st.pop();
            roots[tmp] = n_root;
            if (tmp == cur) break;
        }
    }
    return res;
}

void solve() {
    for(int i = 1; i <= 2 * N; i++) {
        if (visits[i] == 0) SCC(i);
    }
    bool answer = true;
    for (int i = 1; i <= N; i++) {
        if (roots[i] == roots[i + N]) {
            answer = false;
            break;
        }
    }
    if (!answer) {
        cout << "0\n";
        return;
    }
    cout << "1\n";
    for (int i = 1; i <= N; i++) {
        cout << (roots[i] < roots[N + i]) << ' ';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    int a, b, negA, negB;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        a = (a < 0) ? (-a + N) : a;
        b = (b < 0) ? (-b + N) : b;
        negA = (a > N) ? (a - N) : (a + N);
        negB = (b > N) ? (b - N) : (b + N);
        lines[negA].push_back(b);
        lines[negB].push_back(a);
    }
    solve();
}