(3648) 아이돌

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

단계별로 풀어보기

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

 

 

 

2-SAT 문제인데, 상근이는 항상 진출해야 한다. 다시 말해 x_1은 무조건 true가 되어야 한다.

이는 기존 2_CNF에 (x_1∨x_1)이라는 절을 더한 것이라 볼 수 있으며, 간선으로 ￢x_1→x_1을 의미한다. 따라서 1번 노드에서 2번 노드로 이어지는 간선을 추가하면 된다. 나머지는 동일하다.

 

 

 

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

bool solve(int n, int m){
  int cnt= 1, idx= 1;
  
  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);
    }
  }
  adj[1].push_back(2);
  
  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]){
      return false;
    }
  }
  
  return true;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  while(cin >> n >> m){
    cout << (solve(n, m) ? "yes\n" : "no\n");
  }
  
  return 0;
}