[백준 11281] 2-SAT - 4

문제 링크 => 11281번: 2-SAT - 4 (acmicpc.net)

11281번: 2-SAT - 4

---

SCC를 활용한 2-SAT 문제이다.

 

이 문제는 2-SAT - 3 에서 출력해야 할 것이 추가되었다.

 

x1, x2, x3, ..., xn 의 true / false 를 임의로 설정해서 출력하도록 해줘야 한다.

 

2-SAT - 3 에서 만들었던 코드에서 inDegree 를 추가하여 xi, ~xi 의 진입차수를 비교하여 답을 내는것이 중요하다.

 

다음 두가지 조건을 통해 True, False를 내도록 한다

 

(1) xi -> ~xi 일 때 ~xi v ~xi 로 표현 가능하므로 True 결과가 나오기 위해서 이 경우에 xi 는 False 이다. (즉, inDegree[xi] < inDegree[~xi] 인 경우)

 

(2) ~xi -> xi 일 때 xi v xi 로 표현 가능하므로 True 결과가 나오기 위해서 이 경우에 xi 는 True 이다. (즉,  inDegree[~xi] < inDegree[xi] 인 경우)

 

Kosaraju's Algorithm 으로 풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int N, M;
vector<int> go[20001], back[20001];
int inDegree[20001];
bool visited[20001];
stack<int> s;
vector<vector<int>> SCC;

int notX(int x) {
	if (x > N) return x - N;
	return x + N;
}

void dfs1(int x) {
	if (visited[x]) return;
	visited[x] = true;
	for (int i = 0; i < go[x].size(); i++) {
		int next = go[x][i];
		dfs1(next);
	}
	s.push(x);
}

void dfs2(int x, vector<int>& v) {
	if (visited[x]) return;
	visited[x] = true;
	for (int i = 0; i < back[x].size(); i++) {
		int next = back[x][i];
		dfs2(next, v);
	}
	v.push_back(x);
	inDegree[x] = SCC.size();
}

void initialize(int n) {
	for (int i = 1; i <= n; i++) {
		visited[i] = visited[i + n] = false;
	}
}

void solve() {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		if (x < 0) x = abs(x) + N;
		if (y < 0) y = abs(y) + N;

		// ~x -> y
		go[notX(x)].push_back(y);
		back[y].push_back(notX(x));

		// ~y -> x
		go[notX(y)].push_back(x);
		back[x].push_back(notX(y));
	}

	for (int i = 1; i <= N; i++) {
		if (!visited[i]) dfs1(i);
		if (!visited[i + N]) dfs1(i + N);
	}

	initialize(N);

	while (!s.empty()) {
		int x = s.top();
		s.pop();
		if (!visited[x]) {
			vector<int> v;
			dfs2(x, v);
			SCC.push_back(v);
		}
	}

	initialize(N);

	for (int i = 0; i < SCC.size(); i++) {
		for (int j = 0; j < SCC[i].size(); j++) {
			int x = SCC[i][j];
			if (x > N) {
				if (visited[x] || visited[notX(x)]) {
					cout << 0;
					return;
				}
			}
			else {
				if (visited[x] || visited[notX(x)]) {
					cout << 0;
					return;
				}
			}
			visited[x] = true;
		}
		for (int j = 0; j < SCC[i].size(); j++) {
			visited[SCC[i][j]] = false;
		}
	}

	cout << 1 << endl;

	for (int i = 1; i <= N; i++) {
		if (inDegree[i] < inDegree[notX(i)]) cout << 0 << " ";
		else cout << 1 << " ";
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	solve();

	return 0;
}

 

 

Tarjan's Algorithm 으로 풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int N, M, node_num, scc_num;
vector<int> go[20001];
bool finish[20001];
stack<int> s;
vector<vector<int>> SCC;
int dfn[20001], low[20001], inDegree[20001];

int notX(int x) {
	if (x > N) return x - N;
	return x + N;
}

void dfs(int x) {
	// dfn[x] : x번 정점을 몇 번째로 방문했는지
	// low[x] : cross edge(이외의 나머지 모든 간선)를 제외한 간선을 통해서
	// 이동할 수 있는 정점들 중 최소 dfn
	dfn[x] = low[x] = ++node_num;
	s.push(x);

	for (int next : go[x]) {
		if (dfn[next] == 0) { // Tree Edge(DFS 트리 상의 간선)인 경우
			// 방문하지 않은 정점이므로 dfs 실행
			// 자식의 low값으로 현재 정점의 low값을 update
			dfs(next);
			low[x] = min(low[x], low[next]);
		}
		else if (!finish[next]) { // Back Edge(자식에서 조상으로 가는 간선)인 경우
			// 자식의 dfn값으로 현재 정점의 low값을 update
			low[x] = min(low[x], dfn[next]);
		}
	}

	// low[x] < dfn[x] 일 경우에 더 위로 올라갈 수 있음
	if (dfn[x] == low[x]) { // 위로 올라갈 방법이 없음
		vector<int> v;
		while (true) {
			int p = s.top();
			s.pop();

			v.push_back(p);
			finish[p] = true;
			inDegree[p] = SCC.size();
			if (x == p) break;
		}
		SCC.push_back(v);
	}
}

void initialize() {
	for (int i = 1; i <= N; i++) {
		finish[i] = finish[i + N] = false;
	}
}

void solve() {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		if (x < 0) x = abs(x) + N;
		if (y < 0) y = abs(y) + N;

		// ~x -> y
		go[notX(x)].push_back(y);
		// ~y -> x
		go[notX(y)].push_back(x);
	}

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

	initialize();

	for (int i = 0; i < SCC.size(); i++) {
		for (int j = 0; j < SCC[i].size(); j++) {
			int x = SCC[i][j];
			if (x > N) {
				if (finish[x] || finish[notX(x)]) {
					cout << 0;
					return;
				}
			}
			else {
				if (finish[x] || finish[notX(x)]) {
					cout << 0;
					return;
				}
			}
			finish[x] = true;
		}
		for (int j = 0; j < SCC[i].size(); j++) {
			finish[SCC[i][j]] = false;
		}
	}

	cout << 1 << endl;

	for (int i = 1; i <= N; i++) {
		if (inDegree[i] > inDegree[notX(i)]) cout << 0 << " ";
		else cout << 1 << " ";
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	solve();

	return 0;
}