백준 16367번 - TV show Game

www.acmicpc.net/problem/16367

16367번: TV Show Game

 

#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
 
int n, m, a, b, c, cnt;
char f_a, f_b, f_c;
// 그래프의 인접 리스트 표현
vector<vector<int>> adj(10004);
// 각 정점의 컴포넌트 번호. 컴포넌트 번호는 0부터 시작하며
// 같은 강결합 컴포넌트에 속한 정점들의 컴포넌트 번호가 같다.
vector<int> sccID;
// 각 정점의 발견 순서
vector<int> discovered;
// 정점의 번호를 담는 스택
stack<int> st;
int sccCounter, vertexCounter;
// here를 루트로 하는 서브트리에서 역방향 간선이나 교차 간선을
// 통해 갈 수 있는 정점 중 최소 발견 순서를 반환한다.
// (이미 SCC로 묶인 정점으로 연결된 교차 간선은 무시한다.)
int scc(int here) {
    // 이 코드에서 here과 there은 u,v 즉 연결된 정점이라고 생각하면 편하다
    int ret = discovered[here] = vertexCounter++;
    // 스택에서 here를 넣는다. here의 후손들은 모두 스택에서 here 후에 들어간다.
    st.push(here);
    for (int i = 0; i < adj[here].size(); ++i) {
        int there = adj[here][i];
        // (here, there)가 트리 간선
        if (discovered[there] == -1) ret = min(ret, scc(there)); // 아직 방문하지 않았다면
        // there가 무시해야 하는 교차 간선이 아니라면 
        else if (sccID[there] == -1) {
            ret = min(ret, discovered[there]);
        }
 
    }
    // here에서 부모로 올라가는 간선을 끊어야 할지 확인한다.
    if (ret == discovered[here]) {
        //here를 루트로 하는 서브트리에 남아 있는 정점들을 전부 하나의 컴포넌트로 묶는다.
        while (true) {
            int t = st.top();
            st.pop();
            sccID[t] = sccCounter; // sccID의 각 index에는 각 정점이 몇 번째 컴포넌트인지 들어있다.
            cnt = sccCounter;
            if (t == here) break;
        }
        ++sccCounter;
    }
    return ret;
}
 
// tarjan의 SCC알고리즘
vector<int> tarjanSCC() {
    // 배열들을 전부 초기화
    sccID = discovered = vector<int>(adj.size(), -1);
    // 카운터 초기화
    sccCounter = vertexCounter = 0;
    // 모든 정점에 대해 scc() 호출
    for (int i = 1; i <= 2 * n; i++)if (discovered[i] == -1) scc(i);
    return sccID;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> f_a >> b >> f_b >> c >> f_c;
        a = f_a == 'R' ? a : -a;
        b = f_b == 'R' ? b : -b;
        c = f_c == 'R' ? c : -c;
        // a u b 라면 ~a -> b 와 ~b -> a 이 두 간선을 추가해야 한다.
        adj[a > 0 ? n + abs(a) : abs(a)].push_back(b > 0 ? b : n + abs(b));
        adj[b > 0 ? n + abs(b) : abs(b)].push_back(a > 0 ? a : n + abs(a));
        adj[c > 0 ? n + abs(c) : abs(c)].push_back(b > 0 ? b : n + abs(b));
        adj[b > 0 ? n + abs(b) : abs(b)].push_back(c > 0 ? c : n + abs(c));
        adj[a > 0 ? n + abs(a) : abs(a)].push_back(c > 0 ? c : n + abs(c));
        adj[c > 0 ? n + abs(c) : abs(c)].push_back(a > 0 ? a : n + abs(a));
    }
    // tarjan 알고리즘으로 구했기 때문에 위상정렬의 역순으로 구해져 있다.
    vector<int> temp = tarjanSCC();
 
    // x와 ~x가 한 scc안에 있는지 없는지 판단 -> 없다면 SAT
    // 간단한 정리 : p -> q라는 명제에서 p가 거짓이면 q는 참이든 거짓이든 상관없음. but p가 참이면 q도 반드시 참이어야 함!
    // 그렇다면 한 scc안에 하나라도 true라면 전부 true여야 함. -> 이 때 x와 ~x가 같은 scc안에 있다면 위의 조건 불만족
    // 즉, 한 scc안에 자신과 반대되는 명제가 없다면 SAT
 
    int stop = 0;
    for (int i = 1; i <= n; i++) {
        if (temp[i] == temp[n + i]) {
            stop = 1;
            break;
        }
    }
    if (stop == 1) {
        cout << "-1" << "\n";
        return 0;
    }
 
    // 이 문제의 해결방법
    // 위상정렬 -> 먼저 만나는 xi 또는 ~xi 를 false로 설정! (역은 true로 설정)
 
    // 즉, 먼저 위상정렬 된 상태로 바꿔야 한다.
    vector<pair<int, int>>correct_scc;
    for (int i = 1; i <= 2 * n; i++) correct_scc.push_back(make_pair(temp[i], i));
    sort(correct_scc.begin(), correct_scc.end(), greater<pair<int, int>>()); // 정렬을 통해 드디어 제대로 된 위상정렬 순서를 얻었다!
 
    vector<int>ans(2 * n + 1, -1);
    for (int i = 0; i < correct_scc.size(); i++) {
        int x = correct_scc[i].second;
        if (ans[x] == -1) { // 아직 true인지 false인지 모를 때 (방문하지 않았을 때), 자신은 false, 역은 true
            ans[x] = 0;
            ans[x <= n ? n + x : x - n] = 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (ans[i] == 0)cout << 'B';
        else cout << 'R';
    }
    cout << "\n";
}