[BOJ / 2-SAT] 11280 2-SAT - 3

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

11280번: 2-SAT - 3

 

11280 2-SAT-3

알고리즘 : 2-SAT-3 / 강한연결요소(SCC)

SCC 알고리즘를 활용한 알고리즘으로 2-SAT이라는 알고리즘이 있습니다. 전에 휴리스틱으로 풀었던 변수 3개까지 항을 가진 3-SAT은 NP문제인 반면 변수가 2개인 2-SAT은 강한연결요소를 이용하여 풀이할 수 있습니다.

(X_i V X_j)인 경우 !X_i에 X_j를, !X_j에 X_i를 인접간선에 넣어주고 SCC를 구해줍니다.

같은 집합내에 NOT X_i가 존재하는 지 확인만 하면 되므로 자료구조 set을 이용하여 풀이하였습니다.

 

< CODE >

#include <iostream>
#include <vector>
#include <cmath>
#include <stack>
#include <set>

using namespace std;

#define MAX 10005

vector<int> adj[2][MAX];
int isVisited[2][MAX];
bool isFinished[2][MAX];
stack<int> s;
int cnt = 0;
bool result = true;

int DFS(int v)
{
	int p = ++cnt;
	bool isMinus = v < 0;
	int basisV = v;
	
	s.push(v);
	
	v = abs(v);
	isVisited[isMinus][v] = p;
	
	for(int i = 0; i < adj[isMinus][v].size(); i++)
	{
		int to = adj[isMinus][v][i];
		int isTminus = to < 0;
		
		if(!isVisited[isTminus][abs(to)])
		{
			p = min(p, DFS(to));
		}
		else if(!isFinished[isTminus][abs(to)])
		{
			p = min(p, isVisited[isTminus][abs(to)]);
		}
	}
	
	if(p == isVisited[isMinus][v])
	{
		set<int> scc;
		
		while(!s.empty())
		{
			int top = s.top(); s.pop();
			int isM = top < 0;
			
			isFinished[isM][abs(top)] = true;
			
			if(scc.count(abs(top)))
				result = false;
			
			if(basisV == top)
				break;
			
			scc.insert(abs(top));
		}
	}
	
	return p;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n, m;
	
	cin >> n >> m;
	
	while(m--)
	{
		int f, t;
		
		cin >> f >> t;
		
		bool chkF = -f < 0;
		bool chkT = -t < 0;
		
		adj[chkT][abs(t)].push_back(f);
		adj[chkF][abs(f)].push_back(t);
	}
	
	for(int i = 1; i <= n; i++)
	{
		if(!isVisited[0][i])
			DFS(i);
		if(!isVisited[1][i])
			DFS(-i);
	}
	
	cout << result << '\n';
	
	return 0;
}

시간 : 48ms

 

태그 : #백준 2-SAT 3 #백준 투셋 3 #boj 투셋 #11280 2-SAT 3 #11280 2 SAT # 2-SAT 알고리즘