[BOJ / 2-SAT] 11281 2-SAT - 4

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

11281번: 2-SAT - 4

 

11281 2-SAT - 4

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

이전 글에서 풀었던 2-SAT-3의 심화 문제입니다. 이전 문제는 가능한지 판별만 하였다면,

이번 문제는 가능한 케이스 한 개를 같이 출력하여야 합니다. (스페셜 저지)

isVisited 변수는 SCC를 구성하는 순간 쓸모가 없어지므로 이 변수에 몇 번째 SCC인지를 저장합니다.

그렇게 모든 정점을 SCC 순번이 작은대로 정렬하면 자연스럽게 위상정렬을 한 것처럼 정리가 되어 풀이할 수 있습니다.

 

 

< CODE >

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

using namespace std;

#define MAX 10007

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

int result[MAX];
int SCC;
pair<int,int> p[MAX * 2];

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])
	{
		while(!s.empty())
		{
			int top = s.top(); s.pop();
			int isM = top < 0;
			
			isVisited[isM][abs(top)] = SCC + 1;
			isFinished[isM][abs(top)] = true;
			
			if(basisV == top)
				break;
		}
		
		SCC++;
	}
	
	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);
	}
	
	
	for(int j = 1; j <= n; j++)
	{
		result[j] = -1;
		
		if(isVisited[0][j] == isVisited[1][j])
		{
			cout << "0\n";
			return 0;
		}
		
		p[j * 2] = make_pair(isVisited[0][j], j);
		p[j * 2 + 1] = make_pair(isVisited[1][j], -j);
	}
	
	sort(p + 2, p + n * 2 + 2);
	
	for(int i = n*2+2; i >= 2; i--)
	{
		int cur = p[i].second;
		bool isCminus = cur < 0;
		cur = abs(cur);
		
		if(result[cur] == -1)
			result[cur] = isCminus;
	}
	
	cout << "1\n";
	
	for(int i = 1; i <= n; i++)
		cout << result[i] << ' ';
	
	return 0;
}

시간 : 32ms

 

태그 : #BOJ 2-SAT-4 #BOJ 2-SAT 4 #11281 2-SAT #11281 2-SAT 4 #백준 2-SAT-4 #SCC