[백준] 11281 2-SAT -4

2-SAT -3 문제에 이어서 이번엔 식 f를 만족하는 해를 하나 구하는게 문제입니다

위에서는 타잔알고리즘을 이용해 2-SAT문제를 SCC로 묶어서 한 SCC내에 두 정점이 존재하는지 확인을 했습니다.

 

이때 SCC별로 묶는다면 이 그래프는 사이클이 없는 유향 그래프 , DAG가 됩니다.

따라서 이 사이클이 없는 유향 그래프를 이용하면 해를 하나 정할 수 있게 됩니다.

 

들어오는 간선이 없는 정점부터 시작해서 간선을 하나씩 지워갈겁니다.

이때 그 정점을 FALSE라고 가정을 하게 되면, 그 이후 접근할 정점은 TRUE든 FALSE든 관계가 없습니다.

반대로 TRUE라고 가정을하면 그 이후 접근할 정점이 FALSE가 되면 안되므로, 모순이 발생할 수 있습니다.

 

따라서 들어오는 간선이 없는 정점부터 시작해 가능한 한 FALSE로 가정을 할겁니다.

 

이때 말하는 정점은 하나의 SCC를 의미하는데, 하나의 SCC안에서는 반드시 모든 정점이 같은값을 가져야 합니다.

왜냐하면 한 사이클에 대해 TRUE와 FALSE가 동시에 존재한다면 TRUE->FALSE로 가는 간선이 존재하기 때문입니다.

따라서 그 SCC안에서도 모든 정점이 FALSE가 될 수 있도록 들어오는 간선이 없는, 즉 위상정렬된 순서대로 FALSE로 가정을 한다면 모든 정점에 대해 TRUE/FALSE를 추릴 수 있게됩니다.

 

	#include<bits/stdc++.h>

	using namespace std;
	typedef pair<int, int> pi;
	int N, M, A, B;
	vector<pi> cl;
	int v[20001], s[20001];
	int cnt = 0, num = 0;
	vector<int>adj[20001];
	vector<int>st;
	vector<vector<int>>scc;
	int dfs(int k) {
		int parent = v[k] = ++cnt;
		st.push_back(k);
		for (auto r : adj[k]) {
			if (!v[r]) {
				parent = min(parent, dfs(r));
			}
			else if (!s[r]) {
				parent = min(parent, v[r]);
			}
		}

		if (v[k] == parent) {
			++num;
			vector<int>temp;
			while (auto t = st.back()) {
				st.pop_back();
				s[t] = num;
				temp.push_back(t);
				if (t == k)break;
			}
			scc.push_back(temp);
		}
		return parent;
	}
	void tarjan() {
		for (int i = 1; i <= 2 * N; i++) {
			if (!v[i])
				dfs(i);
		}
	}
	bool SAT2() {
		tarjan();
		for (int i = 1; i <= 2 * N; i += 2) {
			if (s[i] == s[i + 1])return false;
		}
		return true;
	}
	int main() {
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);

		cin >> N >> M;
		for (int i = 0; i < M; i++) {
			cin >> A >> B;
			int a, na, b, nb;
			if (A > 0) {
				a = A * 2 - 1;
				na = A * 2;	
			}
			else {
				a = -A * 2;
				na = -A * 2 - 1;
			}

			if (B > 0) {
				b = B * 2 - 1;
				nb = B * 2;
			}
			else {
				b = -B * 2;
				nb = -B * 2 - 1;
			}
			adj[nb].push_back(a);
			adj[na].push_back(b);
		}
		if (SAT2()) {
			cout << 1 << "\n";
			vector<pi>topo;
			int ans[20001];
			memset(ans, -1, sizeof(ans));
			for (int i = 1; i <= 2 * N; i++) {
				topo.push_back({ s[i],i });
			}
			sort(topo.begin(), topo.end(), greater()); //모든 정점에 대해 위상정렬
			for (int i = 0; i < topo.size(); i++) {
				auto r = topo[i].second;
				bool T = r % 2; //0이면 true 1이면 false
				int idx;
				idx = T ? r : r - 1;
				if (ans[idx] != -1)continue;
				ans[idx] = T ? 0 : 1;  //true값만 출력하면 됩니다.
			}
			for (int i = 1; i <= 2*N; i+=2) {
				cout << ans[i] << " ";
			}
		}
		else cout << 0;
	}

타잔 알고리즘을 사용하면 장점이 있습니다.

타잔 알고리즘을 사용하면, 애초부터 자식 SCC들 부터 쌓이게 됩니다.

들어오는 간선이 없는 가장 높은 부모 SCC부터 FALSE로 정해주어야 하는데

타잔알고리즘에서 label을 배열s에 저장하므로

별도의 처리없이 정렬이 가능하게 됩니다.