BOJ 11280 2-SAT - 3

1 개요

BOJ 11280 2-SAT - 3

• 백준 온라인 저지 11280번 문제
• 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;

const int MAX = 20001;
int N, M;
vector<int> graph[MAX];
int visited[MAX] = {0};
int sccId[MAX] = {0}, sccCounter = 0, vertexCounter = 0;
stack<int> S;

int findSCC(int u) {
    int ret = visited[u] = ++vertexCounter;
    S.push(u);
    for(int v : graph[u]) {
        if(!visited[v]) ret = min(ret, findSCC(v));
        else if(!sccId[v]) ret = min(ret, visited[v]);
    }
    if(ret == visited[u]) {
        ++sccCounter;
        while(true) {
            int t = S.top();
            S.pop();
            sccId[t] = sccCounter;
            if(t == u) break;
        }
    }
    return ret;
}

void solve() {
    for(int i = 1; i <= 2*N; i++) {
        if(!visited[i]) findSCC(i);
    }
    for(int i = 1; i <= N; i++) {
        if(sccId[i] == sccId[i + N]) {
            cout << 0;
            return;
        }
    }
    cout << 1;
}

int getIndex(int x) {
    return x > 0 ? x : -x + N;
}

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