(11281) 2-SAT - 4

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

단계별로 풀어보기

48단계(강한 연결 요소) 6번째

 

 

 

이전 문제와 같은 2-SAT 문제인데 이번에는 가능한 경우 해까지 출력해야 한다.

2-SAT 그래프에서 X에서 Y로 가는 간선은 논리적 명제 X→Y이다. 이때 X가 true라면 Y도 항상 true여야 하지만, X가 false라면 Y는 true이든 false이든 상관없이 이 명제는 참(Vacuous Truth)이다.

SCC를 위상 정렬한 뒤 어떤 x_i에 대해 x_i와 ￢x_i 중 먼저 나오는 쪽에 false를 부여한다고 치자(￢x_i가 false라는 것은 x_i가 true라는 것이다). 그러면 이 노드에서 시작하는 수많은 간선으로 이루어진 명제들이 항상 참이 된다. 반면 true를 부여한다면 먼저 나온 쪽에서 이어지는 수많은 명제들에 대해 Y도 강제로 true여야 하므로 논리적 모순이 발생할 가능성이 높다. 따라서 먼저 나오는 쪽에 false를 부여하는 것이 이득이다. 답의 존재성은 이미 판별했기 때문에 이렇게 매 순간마다 최선의 선택을 하면 정답인 해를 구할 수 있다.

 

 

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, cnt= 1, idx= 1;
  
  cin >> n >> m;
  
  vector<int> check(2*n+1), scc(2*n+1);
  vector adj(2*n+1, vector<int> ());
  stack<int> st;
  
  while(m--){
    int i, j;
    
    cin >> i >> j;
    
    if(i>0&&j>0){
      adj[2*i-1].push_back(2*j);
      adj[2*j-1].push_back(2*i);
    }else if(i>0){
      adj[2*i-1].push_back(-2*j-1);
      adj[-2*j].push_back(2*i);
    }else if(j>0){
      adj[-2*i].push_back(2*j);
      adj[2*j-1].push_back(-2*i-1);
    }else{
      adj[-2*i].push_back(-2*j-1);
      adj[-2*j].push_back(-2*i-1);
    }
  }
  
  auto dfs= [&](auto self, int now) -> int {
    st.push(now);
    check[now]= cnt++;
    int low= check[now];
    
    for(int next:adj[now]){
      if(!check[next]){
        low= min(low, self(self, next));
      }else if(!scc[next]){
        low= min(low, check[next]);
      }
    }
    
    if(check[now]==low){
      while(true){
        int here= st.top();
        st.pop();
        scc[here]= idx;
        
        if(here==now)  break;
      }
      
      idx++;
    }
    
    return low;
  };
  
  for(int i=1;i<=2*n;i++){
    if(check[i])  continue;
    
    dfs(dfs, i);
  }
  
  for(int i=1;i<=n;i++){
    if(scc[2*i-1]==scc[2*i]){
      cout << 0;
      
      return 0;
    }
  }
  
  cout << "1\n";
  
  for(int i=1;i<=n;i++){
    cout << (scc[2*i]<scc[2*i-1]) << " ";
  }
  
  return 0;
}