[C++] 3648번 아이돌 - 그래프 이론, 강한 연결 요소, 2-sat

1. 문제

• 한 심사위원은 반드시 찬성 또는 반대하는 두 사람을 고른다. 심사위원은 자신이 행사한 두 표 모두 반대되는 결과가 나오면 의심한다. 상근이가 포함된 다음 라운드 진출목록을 만들 수 있는지 없는지 구하시오.

<입력>

• - 1 -   참가자의 수 n, 심사위원의 수 m \(2 \leq n < 1,000, 1 \leq m < 2,000)\)
• - m개의 줄 -   각 심사위원이 행사한 루트의, 정보 a, b \((1 \leq \left| a \right| , \left| b \right| \leq n, \left| a \right| \neq \left| b \right|)\)
  • 정보가 x<0인 경우 반대표, x>0인 경우 찬성표를 던질 것이다.
• 참가자의 번호는 1~n번이다. 상근이는 1번 참가자이다.

<출력>

• 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 "yes", 없으면 "no"를 출력한다.

2. 재정의

• 2-sat + (1 and 1)

3. 해결 방법

• 2-sat + (1 and 1)

4. 실수한 점, 개선할 점

• 1이 반드시 포함된 경우가 1->2가 연결되있다랑 동치는 아닌 듯하다.
• 2*MAX_N개만큼 준비해야 x, ~x를 모두 반영할 수 있다.

 

<코드>

#include <iostream>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

const int MAX_N = 1001;

// <문제>
// 참가자의 수 N, 심사위원의 수 M
int N, M;

// SCC Tarjan Algorithm
vector<int> adj[MAX_N*2];
stack<int> st;
// 짝수: 거짓, 홀수: 참
int discover[MAX_N*2], scc[MAX_N*2];
int sccCnt, sccSize;

int dfs(int no) {
    st.push(no);
    discover[no] = sccCnt++;
    int parent = discover[no];
    
    for(auto next : adj[no]) {
        if(discover[next] == -1)
            parent = min(parent, dfs(next));
        else if(scc[next] == -1)
            parent = min(parent, discover[next]);
    }
    
    if(parent == discover[no]) {
        while(true) {
            int here = st.top();
            st.pop();
            scc[here] = sccSize;
            if(no == here)
                break;
        }
        sccSize++;
    }
    
    return parent;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    while(true) {
        // <초기화>
        for(int i=0; i<MAX_N*2; i++)
            adj[i].clear();
        memset(discover, -1, sizeof discover);
        memset(scc, -1, sizeof scc);
        sccCnt = sccSize = 1;
        
        // <input>
        // 종료 조건
        if(!(cin >> N >> M))
            return 0;
            
        adj[2].push_back(1);
        for(int i=0; i<M; i++) {
            int a, b;
            cin >> a >> b;
            
            if(a<0) a = -a*2;
            else a = a*2-1;
            if(b<0) b = -b*2;
            else b = b*2-1;
            
            // !연산한 것
            int reva, revb;
            if(a%2) reva = a+1;
            else reva = a-1;
            if(b%2) revb = b+1;
            else revb = b-1;
            
            adj[reva].push_back(b);
            adj[revb].push_back(a);
        }
        
        // <SCC Tarjan Algorithm>
        for(int i=1; i<=2*N; i++) {
            if(discover[i] == -1)
                dfs(i);
        }
        
        // 라운드 진출 목록 생성 가능 여부
        bool flag = true;
        for(int i=1; i<=N; i++)
            // 한 명제의 참 거짓이 하나의 SCC에 묶여있을 경우 생성 불가능
            if(scc[i*2] == scc[i*2 - 1]) {
                flag = false;
                break;
            }
        
        // <출력>
        if(flag)
            cout << "yes" << '\n';
        else
            cout << "no" << '\n';
    }
    
    return 0;
}

 

<문제 바로가기>

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

3648번: 아이돌

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.