Cod sursa(job #2592953)

Utilizator AlexBolfaAlex Bolfa AlexBolfa Data 2 aprilie 2020 17:20:57
Problema 2SAT Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <bits/stdc++.h>
#define NMAX (int)(2e5+4)
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for(int i = l; i < r; ++i)
#define rev(i, r, l) for(int i = r - 1; i >= l; --i)
#define ft first
#define sd second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
FILE* fin = fopen("2sat.in", "r");
FILE* fout = fopen("2sat.out", "w");

int n,m,sol[NMAX],cnt;
vector <int> g[NMAX],tg[NMAX],scc[NMAX];

struct SCC_Algo{
    void build_scc(){
        rep(i, 0, n*2+1)
            if(!used[i])
                build_post(i);
        used.reset();
        rev(i, post.size(), 0)
            if(!used[post[i]]){
                dfs(post[i]);
                ++cnt;
            }
    }
    void build_post(int node){
        used[node]=1;
        for(auto to:g[node])
            if(!used[to])
                build_post(to);
        post.pb(node);
    }
    void dfs(int node){
        used[node]=1;
        scc[cnt].pb(node);
        for(auto to:tg[node])
            if(!used[to])
                dfs(to);
    }
    bitset <NMAX> used;
    vector <int> post;
};

SCC_Algo kosaraju;

inline int NOT(const int&);

int main(){
    fscanf(fin, "%d %d", &n, &m);
    rep(i, 0, m){
        int x,y;
        fscanf(fin, "%d %d", &x, &y);
        x+=n;
        y+=n;
        g[NOT(x)].pb(y);
        g[NOT(y)].pb(x);
        tg[y].pb(NOT(x));
        tg[x].pb(NOT(y));
    }
    kosaraju.build_scc();
    rep(i, 0, cnt){
        bool col=0;
        for(auto nd:scc[i])
            col|=sol[nd];
        for(auto nd:scc[i]){
            if((sol[nd] || sol[NOT(nd)]) && sol[nd] != col){
                fprintf(fout, "-1\n");
                exit(0);
            }
            if(col)
                for(auto to:g[nd])
                    sol[to]=1;
            sol[nd]=col;
            sol[NOT(nd)]=!col;
        }
    }
    rep(i, 1, n+1)
        fprintf(fout, "%d ", sol[i+n]);
    return 0;
}
inline int NOT(const int& x){
    return 2*n-x;
}