문제

상근이는 오디션 프로그램 대한민국 아이돌의 예선에 참가중이다.

대한민국 아이돌 오디션 프로그램에서 참가자는 심사위원에게 10분동안 자신의 매력을 발산할 기회를 갖는다. 모든 참가자가 경연이 끝난후에, 심사위원은 모두 모여서 투표를 하게 된다. 각 심사위원은 다음 라운드에 꼭 진출시켰으면 하는 사람(찬성)이나 이번 라운드에서 꼭 탈락시켰으면 하는 사람(반대)을 두 명 고른다. 한 심사위원이 찬성표를 두 개 내는 것과 반대표를 두 개 내는 것도 가능하며, 찬성과 반대를 각각 하나씩 내는 것도 가능하다. 또, 반드시 두 표를 내야 한다.

다음 라운드에 진출하는 참가자의 수는 정해져 있지 않다. 즉, 실력이 참가자의 경연이 모두 나쁜 경우에는 다음 라운드에 진출하는 참가자가 없을 수도 있고, 모두 엄청난 경연을 한 경우에는 모든 참가자기 다음 라운드에 진출할 수도 있다.

상근이는 심판들이 자신의 프로그래밍 능력에 큰 관심을 보이지 않을 것 같아 걱정하고 있다. 따라서, 상근이는 해킹을 이용해서 다음 라운드에 진출하려고 한다. 상근이는 투표 집계 시스템을 해킹해서, 다음 라운드 진출자를 선택하는 프로그램을 바꿔치기 하려고 한다. 하지만, 의심을 받지 않아야 한다.

각 심사위원은 자신이 행사한 두 표 중 적어도 하나는 결과에 영향을 미쳐야 한다고 생각을 한다. 두 표 모두와 반대되는 결과가 나오면, 심사위원은 투표 결과에 대해서 의심을 하게 된다. 예를 들어, 고원섭 심사위원이 박현수 참가자에게 찬성을, 김선영 참가자에게 반대를 한 경우를 생각해보자. 이 경우에 김선영이 다음 라운드에 진출하고, 박현수가 탈락을 하게 된다면, 두 결과가 모두 영향을 미치지 못했기 때문에, 고원섭 심사위원은 투표를 의심하게 된다.

상근이는 심사위원의 의심을 받지 않으면서, 다음 라운드에 진출하는 목록을 만들 수 있는지를 알고 싶어 한다. 당연히 이 목록에는 상근이가 포함되어 있어야 한다. 각 심사위원이 투표한 결과가 주어졌을 때, 상근이가 포함된 다음 라운드 진출 목록을 만들 수 있는지 없는지를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 참가자의 수 n (2 ≤ n < 1000) 과 심사위원의 수 m (1 ≤ m < 2000)이 주어진다.

다음 m개 줄에는 각 심사위원이 행사한 투표의 정보 a와 b가 주어진다. (1 ≤ |a|, |b| ≤ n, |a| ≠ |b|) 정보가 x < 0인 경우에는 그 심사위원이 참가자 |x|에게 반대표를 행사한 것이고, x > 0인 경우는 |x|에게 찬성을 던진 것이다.

참가자의 번호는 1번부터 n번이다. 상근이는 1번 참가자이다. 

출력

각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 ‘yes’를, 없으면 ‘no’를 출력한다.

예제 입력

4 3
1 2
-2 -3
2 4
2 4
1 2
1 -2
-1 2
-1 -2

예제 출력

yes
no

문제 풀이

2-SAT 문제로 그래프를 구성할 때,
1번째 사람이 true인 조건 ~1 -> 1 추가 했다.
(~1,x)라면 x가 true여야 ~1을 1로 변경가능하다
즉, (a ∨ a) 는 절을 하나 추가하여 풀 수 있었다.

문제 답안

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAX_N   1000

int n, m;

vector<int> adj[MAX_N*2+1];
int dfs_num[MAX_N*2+1];
int dfs_low[MAX_N*2+1];
int dfs_count;
bool scc_visited[MAX_N*2+1];
int stack[MAX_N*2], s_top;

void scc(int u){
    dfs_num[u] = dfs_low[u] = ++dfs_count;
    stack[s_top++] = u;
    for(int v : adj[u]){
        if(dfs_num[v] == 0)
            scc(v);
        if(!scc_visited[v])
            dfs_low[u] = min(dfs_low[u], dfs_low[v]);
    }
    if(dfs_num[u] == dfs_low[u]){
        while(1){
            int v = stack[--s_top];
            scc_visited[v] = true;
            if(u == v)  break;
        }
    }
}

int main(){
    while(scanf("%d %d", &n, &m) == 2){
        for(int i = 0,a,b; i < m; ++i){
            scanf("%d %d", &a, &b);
            a = a > 0 ? a : -a+n;
            b = b > 0 ? b : -b+n;
            adj[a<=n ? a+n : a-n].push_back(b);
            adj[b<=n ? b+n : b-n].push_back(a);
        }
        adj[1+n].push_back(1);
        
        for(int i = 1; i <= n*2; ++i)
            if(dfs_num[i] == 0)
                scc(i);
        
        bool vaild = true;
        for(int i = 1; i <= n; ++i)
            if(dfs_low[i] == dfs_low[i+n]){
                vaild = false;
                break;
            }
        
        printf("%s\n", vaild?"yes":"no");
        
        memset(dfs_num, 0, sizeof(dfs_num));
        memset(dfs_low, 0, sizeof(dfs_low));
        memset(scc_visited, false, sizeof(scc_visited));
        dfs_count = 0;
        for(int i = 1; i <= n*2; ++i)
            adj[i].clear();
    }
    return 0;
}

문제 위치 – https://www.acmicpc.net/problem/3648