(16367) TV Show Game

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

단계별로 풀어보기

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

 

 

 

어떤 사람의 추측을 A, B, C라고 하면 이 중 2개 이상이 맞아야 하므로 하나가 틀리면 나머지 둘은 전부 맞아야 한다.

따라서 어떤 사람의 추측을 ￢A→B, ￢A→C, ￢B→A, ￢B→C, ￢C→A, ￢C→B 6가지 명제로 나타낼 수 있다.

i번 램프를 R로 추측한 것을 x_i, B로 추측한 것을 ￢x_i로 두고 2-SAT 문제처럼 풀면 된다.

 

그리고 이 문제를 풀면서 안 테크닉인데, 불리언 변수의 true와 false를 (0,1), (2,3), (4,5), ... 같은 식으로 0-based 인덱싱을 하면 ￢x_i를 x_i^1로 비트NOT 연산자를 이용해 간단하게 표현할 수 있기 때문에 2-SAT 문제는 0-based 인덱싱으로 푸는 게 일반적이라고 한다.

 

 

 

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

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int k, n, cnt= 1, idx= 1;
  
  cin >> k >> n;
  
  vector<int> check(2*k), scc(2*k);
  vector adj(2*k, vector<int> ());
  stack<int> st;
  
  while(n--){
    int l1, l2, l3;
    char c1, c2, c3;

    cin >> l1 >> c1 >> l2 >> c2 >> l3 >> c3;

    l1= 2*(l1-1)+(c1=='B');
    l2= 2*(l2-1)+(c2=='B');
    l3= 2*(l3-1)+(c3=='B');

    adj[l1^1].push_back(l2);
    adj[l1^1].push_back(l3);
    adj[l2^1].push_back(l1);
    adj[l2^1].push_back(l3);
    adj[l3^1].push_back(l1);
    adj[l3^1].push_back(l2);
  }
  
  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=0;i<2*k;i++){
    if(check[i])  continue;
    
    dfs(dfs, i);
  }
  
  for(int i=0;i<k;i++){
    if(scc[2*i]==scc[2*i+1]){
      cout << -1;
      
      return 0;
    }
  }
  
  for(int i=0;i<k;i++){
    cout << (scc[2*i]<scc[2*i+1] ? "R" : "B");
  }
  
  return 0;
}