(라이님 블로그 대회 알고리즘 따라잡기 24) 2-SAT(Satisfiability Problem)

라이님 블로그에서 이번에는 2-SAT(2-Satisfiability Problem)을 배워보았다.

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220803009418&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList

2-SAT 문제(2-Satisfiability Problem) (수정: 2019-11-16)

 

아직도 끝나지 않은 그래프 지옥...★

 

코드는 저번 SCC 코드랑 비슷한 방식으로 작성해보았다.

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

constexpr int MAX = 10000;

int N, M, id = 0, disc[MAX * 2], sccCount = 0;
bool fin[MAX * 2];
vector<int> adj[MAX * 2];
vector<int> sccID(MAX * 2);
stack<int> st;

inline int oppo(int n) { return n % 2 ? n - 1 : n + 1; };

int dfs(int u) {
	disc[u] = ++id;
	st.push(u);

	int parent = disc[u];
	for (int v : adj[u]) {
		if (disc[v] == 0) parent = min(parent, dfs(v));
		else if (!fin[v]) parent = min(parent, disc[v]);
	}

	if (parent == disc[u]) {
		while (true) {
			int t = st.top();
			st.pop();
			fin[t] = true;
			sccID[t] = sccCount;
			if (t == u) break;
		}
		sccCount++;
	}
	return parent;
}

int main() {
	memset(disc, 0, sizeof(disc));
	memset(fin, 0, sizeof(fin));

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int A, B;
		cin >> A >> B;
		A = (A < 0 ? -(A + 1) * 2 : A * 2 - 1);
		B = (B < 0 ? -(B + 1) * 2 : B * 2 - 1);

		adj[oppo(A)].push_back(B); // not A -> B
		adj[oppo(B)].push_back(A); // not B -> A
	}

	for (int i = 0; i < N * 2; i++) {
		if (disc[i] == 0) dfs(i);
	}

	for (int i = 0; i < N; i++) {
		if (sccID[i * 2] == sccID[i * 2 + 1]) {
			cout << "0" << endl;
			return 0;
		}
	}
	cout << "1" << endl;
	return 0;
}

 

 

✨ DFS를 사용하여 위상 정렬을 수행할 수 있는데, 그래프를 DFS로 탐색한 후 각 정점의 종료 시간을 기준으로 역순으로 나열하면 위상 정렬 순서가 된다.

 

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

constexpr int MAX = 10000;

int N, M, id = 0, disc[MAX * 2], sccCount = 0;
bool fin[MAX * 2];
vector<int> adj[MAX * 2];
vector<int> sccID(MAX * 2);
stack<int> st;

inline int oppo(int n) { return n % 2 ? n - 1 : n + 1; };

int dfs(int u) {
	disc[u] = ++id;
	st.push(u);

	int parent = disc[u];
	for (int v : adj[u]) {
		if (disc[v] == 0) parent = min(parent, dfs(v));
		else if (!fin[v]) parent = min(parent, disc[v]);
	}

	if (parent == disc[u]) {
		while (true) {
			int t = st.top();
			st.pop();
			fin[t] = true;
			sccID[t] = sccCount;
			if (t == u) break;
		}
		sccCount++;
	}
	return parent;
}

int main() {
	memset(disc, 0, sizeof(disc));
	memset(fin, 0, sizeof(fin));

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int A, B;
		cin >> A >> B;
		A = (A < 0 ? -(A + 1) * 2 : A * 2 - 1);
		B = (B < 0 ? -(B + 1) * 2 : B * 2 - 1);

		adj[oppo(A)].push_back(B); // not A -> B
		adj[oppo(B)].push_back(A); // not B -> A
	}

	for (int i = 0; i < N * 2; i++) {
		if (disc[i] == 0) dfs(i);
	}

	for (int i = 0; i < N; i++) {
		if (sccID[i * 2] == sccID[i * 2 + 1]) {
			cout << "0" << endl;
			return 0;
		}
	}

	// 각 변수의 참, 거짓값 알아보기
	int result[MAX];
	memset(result, -1, sizeof(result));

	pair<int, int> p[MAX * 2];
	for (int i = 0; i < N * 2; i++) p[i] = make_pair(sccID[i], i);
	sort(p, p + N * 2);

	// SCC 번호가 크면 클수록 DAG 상에서 앞에 있음
	for (int i = N * 2 - 1; i >= 0; i--) {
		int var = p[i].second;
		if (result[var / 2] == -1) result[var / 2] = !(var % 2);
	}
	for (int i = 0; i < N; i++) {
		cout << result[i] << " ";
	}
	cout << endl;

	cout << "1" << endl;
	return 0;
}