11280 : 2-SAT - 3

풀이

그리워져 미치도록 사랑한 그날들이 내 잃어버린 날들이
참 많이 웃고 울었던 그때 그 시절의 우리
니가 떠올라 밤새

코드

#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> vi;
const int n_ = 10000*2+2;
int n, m, cnt, scc[n_], chk[n_], ans[n_];
vi gph[n_];
vector<vi> res;
stack<int> stk;
int getSCC(int now) {
   chk[now] = ++cnt;
   int ret = chk[now];
   stk.push(now);
   for (int nxt : gph[now]) {
       if (!chk[nxt]) ret = min(ret, getSCC(nxt));
       else if (!scc[nxt]) ret = min(ret, chk[nxt]);
   }
   if (ret != chk[now]) return ret;
   res.push_back(vi());
   while (1) {
       int top = stk.top();
       stk.pop();
       scc[top] = res.size();
       res[res.size() - 1].push_back(top);
       ans[top] = res.size();
       if (top == now) break;
   }
   return ret;
}

int f(int u) {
    return u>n ? u-n : u+n;
}

int main() {
    scanf("%d %d", &n, &m);
    while (m--) {
        int u, v;
        scanf("%d %d", &u, &v);
        if (u < 0) u = -u + n;
        if (v < 0) v = -v + n;
        gph[f(u)].push_back(v);
        gph[f(v)].push_back(u);
    }

    for (int i = 1; i <= 2*n; i++) {
        if (!chk[i]) getSCC(i);
    }

    for (int i = 1; i <= n; i++) {
        if (ans[i] == ans[i+n]) return !puts("0");
    }
    puts("1");

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-06 13:49

Read more posts by this author