가위바위보 (백준 2207)

안녕하세요. 오늘은 가위바위보를 할거예요.

문제

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

아이디어

이 문제는 2-sat로 풀면 됩니다.
크게 바꿀건 없습니다.

소스코드

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

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

int dfs(int node)
{
	visit[node] = ++id;
	s.push(node);
	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 (true)
		{
			int cur = s.top();
			s.pop();
			finish[cur] = 1;
			GroupNum[cur] = cnt;
			if (cur == node) break;
		}
	}

	return parent;
}

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

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, M, i, a, b;
	cin >> M >> N;
	for (i = 0; i < M; i++)
	{
		cin >> a >> b;
		a = 2 * (abs(a) - 1) + (a < 0);
		b = 2 * (abs(b) - 1) + (b < 0);

		v[NOT(a)].push_back(b);
		v[NOT(b)].push_back(a);
	}

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

	for (i = 1; i <= N; i++)
		if (GroupNum[i * 2 - 2] == GroupNum[i * 2 - 1]) //불가능하면
		{
			cout << "OTL";
			return 0;
		}
	cout << "^_^";
}

감사합니다.