Cod sursa(job #2900093)

Utilizator betybety bety bety Data 10 mai 2022 09:35:58
Problema 2SAT Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("2sat.in");
ofstream out("2sat.out");
const int lim=2e5+4;
vector<int> vec[2*lim];
vector<int> rev[2*lim];
stack<int> st;
bool ok[2*lim];
int n,m,x,y;
void df(int nod)
{
    ok[nod]=true;
    for(int x:vec[nod])
    if(!ok[x]) df(x);
    st.push(nod);
}
int grupa[2*lim];
int cnt;
void df2(int nod)
{
    ok[nod]=true;
    grupa[nod]=cnt;
    for(int x:rev[nod])
    if(!ok[x]) df2(x);
}
vector<int> v[2*lim];
int other[2*lim];
int val[2*lim];
void d(int nod)
{
    ok[nod]=true;
    for(int x:v[nod])
    if(!ok[x]) d(x);
    st.push(nod);
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;++i)
        in>>x>>y,
        vec[-x+n].push_back(y+n),
        vec[-y+n].push_back(x+n),
        rev[y+n].push_back(-x+n);
        rev[x+n].push_back(-y+n);
    for(int i=0;i<=2*n;++i) if(i!=n)
    if(!ok[i]) df(i);
    memset(ok,0,sizeof(ok));
    while(!st.empty())
    {
        int nod=st.top(); st.pop();
        if(ok[nod]) continue;
        ++cnt;
        df2(nod);
    }
    for(int i=0;i<n;++i)
    if(grupa[i]==grupa[2*n-i])
    {
        out<<-1<<'\n';
        return 0;
    }
    else other[grupa[i]]=grupa[2*n-i],
        other[grupa[2*n-i]]=grupa[i];
    for(int i=0;i<=2*n;++i) if(i!=n)
    for(int x:vec[i]) if(grupa[i]!=grupa[x])
        v[grupa[i]].push_back(grupa[x]);
    memset(ok,0,sizeof(ok));
    for(int i=1;i<=cnt;++i)
    if(!ok[i]) d(i);
    memset(ok,0,sizeof(ok));
    while(!st.empty())
    {
        int nod=st.top(); st.pop();
        if(ok[nod]) continue;
        val[nod]=0;
        val[other[nod]]=1;
        ok[nod]=true;
        ok[other[nod]]=true;
    }
    for(int i=n+1;i<=2*n;++i)
        out<<val[grupa[i]]<<' ';
    out<<'\n';
    return 0;
}