글 읽기 - [C++] 11281번 질문입니다

0000000000 2년 전 0

2-SAT - 3에서 추가로 각 변수의 값을 설정하는 부분을 어떻게 해야 할 지 모르겠습니다. SCC를 구하는 부분은 코라사주로 했습니다

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> adj(20005);
vector<vector<int>> r(20005);
vector<bool> visited(20005);
stack<int> st;
vector<int> scc(20005);
vector<int> res(20005,-1);
vector<pair<int,int>> p;
int n,k;
int f(int x){
    return x%2?x-1:x+1;
}
void dfs(int u){
    visited[u]=true;
    for(int v:adj[u]) if(!visited[v]) dfs(v);
    st.push(u);
}
void dfs2(int u,int c){
    visited[u]=true;
    for(int v:r[u]) if(!visited[v]) dfs2(v,c);
    scc[u]=c;
}
void SCC(){
    for(int i=2;i<=n*2+1;i++) if(!visited[i]) dfs(i);
    fill(visited.begin(),visited.end(),false);
    int c=0;
    while(!st.empty()){
        int i=st.top();
        st.pop();
        if(!visited[i]){
            c++;
            dfs2(i,c);
        }
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>k;
    int u,v;
    while(k--){
        cin>>u>>v;
        u=u>0?u*2:-(u*2)+1;
        v=v>0?v*2:-(v*2)+1;
        adj[f(u)].push_back(v);
        adj[f(v)].push_back(u);
        r[u].push_back(f(v));
        r[v].push_back(f(u));
    }
    SCC();
    for(int i=1;i<=n;i++){
        if(scc[i*2]==scc[i*2+1]){
            cout<<0;
            return 0;
        }
    }
    cout<<"1\n";
    
    //
}

zenith82114 2년 전 1

힌트만 드려 보겠습니다.

변수 x_i가 가져야 할 값은 x_i와 NOT x_i가 각각 속한 scc의 위상관계(=방문 순서, =방문하면서 매긴 번호)와 관련이 있습니다.

0000000000 2년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++] 11281번 질문입니다

0000000000 2년 전 0

zenith82114 2년 전 1

0000000000 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말