아이돌 (백준 3648)

안녕하세요. 오늘은 아이돌이 될거예요.

문제

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

아이디어

이 문제는 2-sat문제입니다.
그런데 무조건 1은 참이여야 하므로 입력에 1 1이 있다고 가정을 합시다.
이것은 1이 참이거나 1이 참이거나(???)라는 뜻입니다. 그러면 무조건 1이 참이 됩니다.
그리고 타잔 알고리즘을 통해서 2-sat문제를 풀어주면 됩니다.

소스코드

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

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

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] = 1;
			if (cur == node) break;
		}
	}

	return parent;
}

int NOT(int x) //인덱스가 0부터 시작 {0,1} {2,3} ...
{
	if (x % 2 == 1) return x - 1;
	return x + 1;
}

bool able(void)
{
	if (GroupNum[0] > GroupNum[1]) return false; //애초에 1이 불가능한 상황
	for (int i = 1; i <= N; i++)
		if (GroupNum[i * 2 - 2] == GroupNum[i * 2 - 1]) //만약 어떤 한 값이 불가능하다면
			return false;
	return true;
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int M, i, a, b;
	while (cin >> N >> M)
	{
		id = 0;
		cnt = 0;

		for (i = 0; i < 2 * N; i++)
			v[i].clear();
		for (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);
		}
		v[1].push_back(0); //무조건 상근이는 되어야 함

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

		if (able()) //가능하다면
			cout << "yes\n";
		else
			cout << "no\n";
	}
}

감사합니다.