[백준 3648] 아이돌

문제

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

 

알고리즘

2-SAT

 

풀이

문제에서 2-SAT의 느낌을 물씬 풍기는 문장이 몇 있습니다. '적어도 하나'라는 문장은 OR을 연상케 하고 OR은 2-CNF에서 하나의 절을 구성합니다. 그리고 한 참가자에 대해 두 가지 선택을 할 수 있다는 점도 True와 False로 연관 지을 수 있으니 2-SAT으로 문제를 접근합시다.

 

심사위원의 의심 없이 다음라운드를 구성할 수 있다면 하나의 참가자에 대해 모순이 되는 경우가 없다는 의미와 같습니다. 즉, 각 정점의 True와 False의 $sccid$가 일치해서는 안됩니다.

상근이가 진출하는 경우는 그래프상에서 상근이의 False 정점이 True 정점보다 위상정렬상 빠른지 확인하면 됩니다.

이전 문제에서 위상정렬상 빠른 정점을 False로 평가하는 것이 True로 평가하는 것보다 항상 이득임을 확인했습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

#define T(x) (x<<1)
#define F(x) (x<<1|1)

int n, m, a, b, VC, SC;

vector<vector<int>> adj;
vector<int> discovered, sccid;
stack<int> st;
int scc(int here) {
    int ret = discovered[here] = VC++;
    st.emplace(here);

    for (auto there : adj[here]) {
        if (discovered[there] == -1) ret = min(ret, scc(there));
        else if (sccid[there] == -1) ret = min(ret, discovered[there]);
    }

    if (ret == discovered[here]) {
        while (1) {
            int t = st.top();
            st.pop();
            sccid[t] = SC;
            if (t == here) break;
        }
        SC++;
    }
    return ret;
}

void OR(int A, int B) {
    adj[A ^ 1].emplace_back(B);
    adj[B ^ 1].emplace_back(A);
}

int main() {
    FAST;
    while (cin >> n >> m) {
        VC = SC = 0;
        adj.clear();
        adj.resize(n << 1);
        discovered.clear();
        sccid.clear();
        discovered = sccid = vector<int>(n << 1, -1);

        while (m--) {
            cin >> a >> b;
            a = a > 0 ? T(a - 1) : F(~a);
            b = b > 0 ? T(b - 1) : F(~b);
            OR(a, b);
        }

        rep(i, n << 1) if (discovered[i] == -1) scc(i);

        bool flag = true;
        for (int i = 0;i < n;++i) if (sccid[i] == sccid[i ^ 1]) {
            flag = false;
            break;
        }

        if (sccid[0] > sccid[1]) flag = false;

        cout << (flag ? "yes" : "no") << '\n';

    }

    return 0;
}