백준 1217번: 하우스 M.D. (C++)

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

1217번: 하우스 M.D.

---

Solved By: 2-SAT, SCC

 

문제 글의 일부분을 가져와봅니다. "House의 규칙이 2 -3이라면, 증세 2가 일어나고 동시에 증세 3이 일어나지 않은 경우 환자가 죽게 된다는 뜻이다." 

>> 이 말인즉슨, 증세 2가 일어나지 않고, 증세 3이 일어난다면 환자는 살 것이고, 증세 3이 일어나고, 증세 2가 일어난다면, 이 또한 환자는 살 것이라는 말입니다.

>> NOT_2 => NOT_3, 3 => 2

 

(아직 2-SAT을 설명할 어휘력이 많이 부족한 거 같습니다..)

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAX 40002
using namespace std;

vector<vector<int>> SCC;
vector<int> adj[MAX];
int visitedOrder[MAX];
int sccNum[MAX];
stack<int> s;
int order = 0, sccCnt = 0;
int n, m;

int dfs(int now){
    int parent = visitedOrder[now] = ++order;
    s.push(now);
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(visitedOrder[next] == -1){
            parent = min(parent, dfs(next));
        }
        else if(sccNum[next] == -1){
            parent = min(parent, visitedOrder[next]);
        }
    }
    
    if(visitedOrder[now] == parent){
        vector<int> scc;
        while(1){
            int temp = s.top(); s.pop();
            scc.push_back(temp);
            sccNum[temp] = sccCnt;
            if(temp == now) break;
        }
        
        SCC.push_back(scc);
        sccCnt++;
    }
    
    return parent;
}

void tarjan(){
    fill(visitedOrder, visitedOrder + MAX, -1);
    fill(sccNum, sccNum + MAX, -1);
    for(int i = 2; i <= 2 * m + 1; i++){
        if(visitedOrder[i] == -1) dfs(i);
    }
}

int main(){
    while(true){
        cin >> n >> m;
        if(n == 0 && m == 0) break;
        
        //init
        SCC.clear();
        for(int i = 0; i < MAX; i++) adj[i].clear();
        order = 0; sccCnt = 0;
        while(!s.empty()) s.pop();
        
        for(int i = 0; i < n; i++){
            int a, b; cin >> a >> b;
            
            int not_a, not_b;
            if(a < 0){
                a = -a; a *= 2;
                a++;
                not_a = a - 1;
            }
            else{
                a *= 2;
                not_a = a + 1;
            }
            
            if(b < 0){
                b = -b; b *= 2;
                b++;
                not_b = b - 1;
            }
            else{
                b *= 2;
                not_b = b + 1;
            }
            
            adj[not_a].push_back(b);
            adj[not_b].push_back(a);
        }
        
        tarjan();
        
        bool flag = 1;
        for(int i = 2; i <= 2 * m; i += 2){
            if(sccNum[i] == sccNum[i + 1]){
                flag = 0; break;
            }
        }
        
        if(flag == 1) cout << 1;
        else cout << 0;
        cout << '\n';
    }
    return 0;
}