boj, 백준) 11281. 2-sat-4

이 문제는 https://www.acmicpc.net/problem/11280 이 문제와 많이 유사합니다. 2-sat의 해의 조건을 알았으면 해를 하나 출력해야되는 문제입니다. 2-sat의 필요조건이 scc와 연관되는건 이해가 됐었는데 실제 해가 있는지는 헷갈렸는데 이 문제로 말끔히 해결됐습니다! 저는 어려워서 풀이를 봤는데 아이디어가 좀 멋져서 한번 생각해보는게 좋을 것 같습니다! 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

__________________________________________________ 스포 방지 _______________________________________________________

 

#include <bits/stdc++.h>
#define Max 200020
using namespace std;
int n, m, my_scc[Max];
vector<int> vt[Max], rvt[Max], scc[Max];
bool visited[Max];
stack<int> st;

void dfs(int x) {
	visited[x] = true;
	for (auto n : vt[x]) {
		if (visited[n]) continue;
		dfs(n);
	}
	st.push(x);
}

void dfss(int x, int y) {
	my_scc[x] = y;
	scc[y].push_back(x);
	visited[x] = true;
	for (auto n : rvt[x]) {
		if (visited[n]) continue;
		dfss(n, y);
	}
}
int f(int x) {
	if (x > n) return x - n; 
	return x + n;
}

int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;
		if (x < 0) x = n - x;
		if (y < 0) y = n - y;
		rvt[x].push_back(f(y));
		rvt[y].push_back(f(x));
		vt[f(y)].push_back(x);
		vt[f(x)].push_back(y);
	}
	for (int i = 1; i <= 2 * n; i++) {
		if (!visited[i]) dfs(i);
	}
	int r = 0;
	memset(visited, 0, sizeof(visited));
	while (!st.empty()) {
		int t = st.top(); st.pop();
		if (visited[t]) continue;
		dfss(t, r++);
	}
	int f = 1;
	for (int i = 1; i <= n; i++) {
		if (my_scc[i] == my_scc[n + i]) f = 0;
	}
	cout << f << "\n";
	if (f == 1) {
		for (int i = 1; i <= n; i++) cout << (my_scc[i] > my_scc[n + i]) << " ";
	}
}

 먼저 (p v q) 가 만족할 때 ((~p) -> (q)) ^ ((~q) -> (p)) 인 것으로 그래프를 그려줬습니다. 그러면 scc 상에서 어떤 한점이 참이면 나머지 점들도 모두 참임을 알 수 있죠. 그래서 scc 마다 참 거짓을 정해주면 됩니다. 

 

 이제 xi가 맞냐 ~xi가 맞냐가 관건입니다. (xi v xj) 인 경우를 생각해봅시다. 

먼저 위상정렬이 먼저된 scc 에서 위상정렬이 나중에 된 scc 로만 방향선분이 가능한걸 알 수 있습니다. 그래서 xj 가 거짓이라면 scc(~xj) <= scc(xi), xi 가 거짓이라면 scc(~xi) <= scc(xj) 인 것을 알 수 있습니다. 이제 xi 가 맞을 조건을

scc[xi] > scc[~xi] 로 둔다 생각합시다. 만약 xj가 거짓이라면 

scc[~xi] <= scc[xj] < scc[~xj] <= scc[xi] 이므로 scc[~xi] < scc[xi] 임을 알 수 있습니다. 즉 xi가 참이게 됩니다. 반대경우도 마찬가지로 되고 해를 알 수 있습니다. 와... 이런 아이디어는 어떻게 생각하는지 좀 멋있습니다!!!!