완벽한 선거! (백준 3747)

안녕하세요. 오늘은 완벽한 선거를 할 거예요.

문제

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

아이디어

전형적인 2-sat 문제입니다.

소스코드

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

vector <int> v[2020];
stack <int> s;
int visit[2020] = { 0 }, finish[2020] = { 0 }, id = 0, cnt = 0;
int GroupNum[2020] = { 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();
			GroupNum[cur] = cnt;
			finish[cur] = true;
			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, a, b;
	while (cin >> N >> M)
	{
		for (int i = 0; i < 2 * N; i++)
		{
			v[i].clear();
			visit[i] = 0;
			finish[i] = 0;
			id = 0;
			cnt = 0;
			GroupNum[i] = 0;
		}

		for (int i = 0; i < M; i++)
		{
			cin >> a >> b;
			a = (abs(a) - 1) * 2 + (a < 0);
			b = (abs(b) - 1) * 2 + (b < 0);
			v[NOT(a)].push_back(b);
			v[NOT(b)].push_back(a);
		}

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

		bool able = true;
		for (int i = 1; i <= N; i++)
			if (GroupNum[i * 2 - 2] == GroupNum[i * 2 - 1])
				able = false;
		if (able) cout << "1\n";
		else cout << "0\n";
	}
}

감사합니다.