boj, 백준) 16367. TV Show Game

결국 심사위원의 세 선택중 두개는 정답과 같아야 하므로 세선택을 a,b,c 라 하면 (a v b) ^ (b v c) ^ (c v a) 로 나타낼 수 있어서 2-sat 문제가 됩니다. 단계별로 풀기에서 2-sat 으로 되어있길래 쉽게 풀었는데 2-sat 인걸 몰랐으면 좀 어려웠을 수도 있을 것 같습니다 ㅠㅠ  

 

#include <bits/stdc++.h>
#define Max 10100
using namespace std;
int n, m, my_scc[Max];
vector<int> vt[Max], rvt[Max], scc[Max];
bool visited[Max];
stack<int> st;

int f(int x) {
	if (x > n) return x - n;
	return x + n;
}

void g(int x, int y) {
	rvt[x].push_back(f(y));
	rvt[y].push_back(f(x));
	vt[f(x)].push_back(y);
	vt[f(y)].push_back(x);
}

void dfs(int x) {
	visited[x] = true;
	for (auto n : vt[x]) {
		if (visited[n]) continue;
		dfs(n);
	}
	st.push(x);
}

void dfss(int x, int y) {
	visited[x] = true;
	for (auto n : rvt[x]) {
		if (visited[n]) continue;
		dfss(n, y);
	}
	scc[y].push_back(x);
	my_scc[x] = y;
}

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, z; char a, b, c;
		cin >> x >> a >> y >> b >> z >> c;
		if (a == 'B') x = f(x);
		if (b == 'B') y = f(y);
		if (c == 'B') z = f(z);
		g(x, y); g(y, z); g(z, x);
	}
	
	for (int i = 1; i <= 2 * n; i++) {
		if (!visited[i]) dfs(i);
	}
	int r = 0;
	memset(visited, 0, sizeof(visited));
	while (!st.empty()) {
		int t = st.top(); st.pop();
		if (visited[t]) continue;
		dfss(t, r++);
	}
	int f = 1;
	for (int i = 1; i <= n; i++) {
		if (my_scc[i] == my_scc[n + i]) f = 0;
	}
	if (f == 0) cout << "-1";
	else {
		for (int i = 1; i <= n; i++) {
			cout << (my_scc[i] > my_scc[n + i] ? 'R' : 'B');
		}
	}
}