TV Show Game (백준 16367)

안녕하세요. 오늘은 티비 게임을 할 거예요.

문제

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

아이디어

세 문제중 하나가 틀리면 나머지 두개는 무조건 맞아야합니다.
즉 세 문제 A,B,C가 있을 때 ~A -> B,C 이여야 합니다. B랑 C도 똑같이 하면 됩니다. 이것이 2-sat입니다.

소스코드

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

vector <int> v[10101];
stack <int> s;
int GroupNum[10101] = { 0 }, visit[10101] = { 0 }, finish[10101] = { 0 }, id = 0, cnt = 0;

int dfs(int node)
{
	s.push(node);
	visit[node] = ++id;
	int parent = id;

	for (int next : v[node])
		if (!visit[next])
			parent = min(parent, dfs(next));
		else if (!finish[next])
			parent = min(parent, visit[next]);

	if (parent == visit[node])
	{
		cnt++;
		while (s.size())
		{
			int cur = s.top();
			s.pop();
			GroupNum[cur] = cnt;
			finish[cur] = 1;
			if (cur == node) break;
		}
	}

	return parent;
}

int NOT(int x)
{
	if (x % 2 == 0) return x + 1;
	return x - 1;
}

int num(int a, char c)
{
	if (c == 'R') return a;
	return NOT(a);
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int k, N, i, a, b, c;
	char x, y, z;

	cin >> k >> N;
	for (i = 0; i < N; i++)
	{
		cin >> a >> x >> b >> y >> c >> z;
		a = (abs(a) - 1) * 2 + (x == 'B');
		b = (abs(b) - 1) * 2 + (y == 'B');
		c = (abs(c) - 1) * 2 + (z == 'B');

		v[NOT(a)].push_back(b);
		v[NOT(a)].push_back(c); //a가 아니면 무조건 b랑 c
		v[NOT(b)].push_back(a);
		v[NOT(b)].push_back(c); //b가 아니면 무조건 a랑 c
		v[NOT(c)].push_back(a);
		v[NOT(c)].push_back(b); //c가 아니면 무조건 a랑 b
	}

	for (i = 0; i < 2 * k; i++)
		if (!visit[i])
			dfs(i);

	for (i = 1; i <= k; i++)
	{
		if (GroupNum[i * 2 - 2] == GroupNum[i * 2 - 1])
		{
			cout << -1;
			return 0;
		}
	}

	for (i = 1; i <= k; i++)
	{
		if (GroupNum[i * 2 - 2] < GroupNum[i * 2 - 1]) cout << 'R';
		else cout << 'B';
	}
}

감사합니다.