백준 11281(2-SAT_4) C++

문제

11281번: 2-SAT - 4

이전에 있던 문제 에서 주어진 변수 n개를 각각 true인지 false인지 출력해주는 문제입니다.

변수가 true 이면 1을 출력하고, false이면 0을 출력합니다.

 

나머지 코드들은 모두 동일하므로 추가된 코드를 설명하겠습니다.

reverse(SCC.begin(), SCC.end());

scc의 벡터를 뒤집습니다.

왜냐하면 위상정렬로 정렬해주어야 하기 때문입니다.

타잔 알고리즘 특성상 scc의 번호가 클 수록 DAG에서 앞에 있습니다. 

따라서 SCC의 벡터를 뒤집어 주면 위상정렬의 형태로 됩니다.

for (auto cur : SCC) {
	for (auto nxt: cur) {
		if (A[nxt])continue;
		A[nxt] = 0;
		A[rev(nxt)] = 1;
	}
}
for (int i = 1; i <= n; i++)cout << A[i] << ' ';

위상정렬된 SCC를 탐색하면서 먼저 나오는 노드에 false를 할당하고 그 노드의 not은 자동적으로 true를 할당합니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
vector<ll>v[100001]; //주어진 그래프 정보 저장
ll dfsn[100001];//방문 순서를 저장할 배열
ll scc_count; //scc의 갯수를 세는 변수
ll sn[100001]; //x번 정점이 몇번째 scc에 포함되어 있는지 알려주는 배열
vector<vector<ll>>SCC; //SCC를 벡터로 저장한 벡터의 벡터
stack<ll>st;
bool fin[100001];//x번쨰 정점이 scc추출이 끝났는지 확인
ll A[100001];
ll n, m, a, b,cnt;
ll dfs(ll x);
ll rev(ll x);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m;
    while (m--) {
        cin >> a >> b;
        if (a < 0)a = abs(a) + n;
        if (b < 0)b = abs(b) + n;
        v[rev(a)].push_back(b);
        v[rev(b)].push_back(a);
    }
    for (int i = 1; i <= 2 * n; i++) {
        if (dfsn[i])continue;
        dfs(i);
    }
    for (int i = 1; i <= n; i++) {
        if (sn[i] == sn[i + n]) {
            cout << "0";
            return 0;
        }
    }
    cout << "1" << '\n';
    reverse(SCC.begin(), SCC.end());
 
    for (auto cur : SCC) {
        for (auto nxt: cur) {
            if (A[nxt])continue;
            A[nxt] = 0;
            A[rev(nxt)] = 1;
        }
    }
    for (int i = 1; i <= n; i++)cout << A[i] << ' ';
    
    return 0;
}
ll dfs(ll x) { //x와 x의 자손들 중 올라갈 수 있는 최소의 dfsn값을 return(제일 위로 어디까지 갈 수 있는지)
    dfsn[x] = ++cnt; //방문순서를 계속해서 저장
    st.push(x);
    ll ret = dfsn[x];
    for (ll nxt : v[x]) {
        if (!dfsn[nxt])ret = min(ret, dfs(nxt));
        else if (!fin[nxt])ret = min(ret, dfsn[nxt]);
    }
    if (ret == dfsn[x]) { //자신과 자신의 자손들 중 자신의 조상으로 가는 간선이 없을 경우
        vector<ll>curSCC;
        while (1) { //scc를 stack에서 빼주는 작업
            ll a = st.top();
            st.pop();
            curSCC.push_back(a);
            fin[a] = true;
            sn[a] = scc_count;
            if (a == x)break;
        }
        SCC.push_back(curSCC);
        scc_count++;
    }
    return ret;
}
ll rev(ll x) {
    if (x <= n)return x + n;
    return x - n;
}