BOJ 3648 - 아이돌 링크
(2023.04.28 기준 P3)

문제

m명의 심사위원이 각각 n명의 참가자 중 찬성이나 반대를 두 명 고른다. 1번 참가자인 상근이가 꼭 뽑혀야 하며, 각 심사위원의 두 표 중 적어도 하나는 반영되어야 한다.
이 때, 상근이가 뽑히는 결과가 가능한지 판별

알고리즘

두 표 중 적어도 하나는 반영되어야 한다는 점은 2-SAT.

풀이

문제를 해석하면 (a1 or b1) and (a2 or b2) and ... and (am or bm) 이다. 이는 곧 2-SAT이다.
그런데 문제점이 하나가 있다. 상근이가 꼭 뽑혀야 한다. 이를 어떻게 나타내야 할까?

(a or b) 절은 곧 (-a -> b), (-b -> a)이다. 이 뜻은 a가 역이면 b는 무조건 참. b가 역이면 a는 무조건 참이라는 뜻이다.
자, 상근이는 1번. 1번이 꼭 뽑혀야 한다. 그렇다면? (1 or 1) 절이다. 그러면 결국 (-1 -> 1) 간선을 따로 하나 더 추가하면 된다.

코드

• C++

#include <bits/stdc++.h>
#define add_clause(a, b) graph[a].push_back(b), reverse_graph[b].push_back(a)
using namespace std;

const int MAXN = 1999; // 999 * 2 + 1

int ids[MAXN], idx;
bool visited[MAXN];
vector<int> graph[MAXN], reverse_graph[MAXN], q;

void dfs(int i){
    visited[i] = true;
    for (int j: graph[i]) if (!visited[j]) dfs(j);
    q.push_back(i);
}

void reverse_dfs(int i){
    visited[i] = true;
    ids[i] = idx;
    for (int j: reverse_graph[i]) if (!visited[j]) reverse_dfs(j);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, N;
    while (cin >> n >> m){

        N = n * 2 + 1;
        for (int i = 0; i < N; i++) graph[i].clear(), reverse_graph[i].clear();

        // a or b 간선 추가
        for (int i = 0, a, b, not_a, not_b; i < m; i++){
            cin >> a >> b;
            if (a > 0) not_a = a + n;
            else a = -a + n, not_a = a - n;
            if (b > 0) not_b = b + n;
            else b = -b + n, not_b = b - n;
            add_clause(not_a, b);
            add_clause(not_b, a);
        }

        // 1 or 1 간선 추가
        add_clause(1 + n, 1);

        // 코사리주
        // 정방향 탐색으로 정점 쌓기
        fill(visited, visited + N, false);
        for (int i = 1; i < N; i++) if (!visited[i]) dfs(i);

        // 역방향 탐색으로 SCC 찾기
        fill(visited, visited + N, false);
        fill(ids, ids + N, -1);
        idx = 0;
        while (!q.empty()){
            int i = q.back(); q.pop_back();
            if (!visited[i]) reverse_dfs(i), idx++;
        }

        // 역과 같은 SCC에 속하면 모순(거짓)
        bool is_true = true;
        for (int i = 1; i <= n; i++) if (ids[i] == ids[i + n]){
            cout << "no\n";
            is_true = false;
            break;
        }
        if (is_true) cout << "yes\n";
    }
}

• Python

import sys; input = sys.stdin.readline
sys.setrecursionlimit(10000)

def dfs(i):
    visited[i] = True
    for j in graph[i]:
        if not visited[j]:
            dfs(j)
    queue.append(i)

def reverse_dfs(i):
    visited[i] = True
    ids[i] = idx
    for j in reverse_graph[i]:
        if not visited[j]:
            reverse_dfs(j)

while True:
    try:
        n, m = map(int, input().split())
    except:
        break

    N = n * 2 + 1
    graph = [[] for _ in range(N)]
    reverse_graph = [[] for _ in range(N)]

    # a or b 간선 추가
    for _ in range(m):
        a, b = map(int, input().split())
        graph[-a].append(b)
        reverse_graph[b].append(-a)
        graph[-b].append(a)
        reverse_graph[a].append(-b)

    # 1 or 1 간선 추가
    graph[-1].append(1)
    reverse_graph[1].append(-1)

    # 코사리주
    # 정방향 탐색으로 정점 쌓기
    queue = []
    visited = [False] * N
    for i in range(1, N):
        if not visited[i]:
            dfs(i)

    # 역방향 탐색으로 SCC 찾기
    visited = [False] * N
    ids = [-1] * N
    idx = 0
    while queue:
        i = queue.pop()
        if not visited[i]:
            reverse_dfs(i)
            idx += 1

    # 역과 같은 SCC에 속하면 모순(거짓)
    for i in range(1, n + 1):
        if ids[i] == ids[-i]:
            print('no')
            break
    else:
        print('yes')