BOJ 16367 TV Show Game

1 개요

BOJ 16367 TV Show Game

• 백준 온라인 저지 16367번 문제
• BOJ 44단계

2 C++

#include <bits/stdc++.h>
using namespace std;

int K, N;
vector<vector<int>> graph;
vector<int> visited, scc_arr;
stack<int> st;
int idx = 1, scc_num = 1;

int SCC(int node) {
    visited[node] = idx++;
    st.push(node);
    int root = visited[node];
    for (int next : graph[node]) {
        if (!visited[next]) root = min(root, SCC(next));
        else if (!scc_arr[next]) root = min(root, visited[next]);
    }
    if (root == visited[node]) {
        while (true) {
            int top = st.top();
            st.pop();
            scc_arr[top] = scc_num;
            if (top == node) break;
        }
        scc_num++;
    }
    return root;
}

void solve() {
    for (int i = 1; i <= 2 * K; ++i) {
        if (!visited[i]) SCC(i);
    }
    for (int i = 1; i <= K; ++i) {
        if (scc_arr[i] == scc_arr[i + K]) {
            cout << -1;
            return;
        }
    }
    for (int i = 1; i <= K; ++i) {
        cout << (scc_arr[i] > scc_arr[i + K] ? 'B' : 'R');
    }
}

int neg(int a) {
    return (a <= K) ? a + K : a - K;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> K >> N;
    graph.resize(2 * K + 1);
    visited.resize(2 * K + 1);
    scc_arr.resize(2 * K + 1);
    for (int i = 0; i < N; ++i) {
        int a, b, c;
        char RB1, RB2, RB3;
        cin >> a >> RB1 >> b >> RB2 >> c >> RB3;
        if (RB1 == 'B') a += K;
        if (RB2 == 'B') b += K;
        if (RB3 == 'B') c += K;
        graph[neg(a)].push_back(b);
        graph[neg(b)].push_back(a);
        graph[neg(b)].push_back(c);
        graph[neg(c)].push_back(b);
        graph[neg(c)].push_back(a);
        graph[neg(a)].push_back(c);
    }
    solve();
}