Cod sursa(job #2299187)

Utilizator driver71528@gmail.comTerec Andrei-Sorin [email protected] Data 9 decembrie 2018 00:16:26
Problema 2SAT Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <stack>
#include <vector>
#include <set>
#include <fstream>
#define UNVISITED -1
using namespace std;
stack<int> s;
int ID;
struct NOD
{
    int id,low,rez;

    bool onstack;
    NOD()
    {
        onstack=false;
        id=UNVISITED;
        rez=-1;
    }
};
vector<int> v[200003];
NOD nod[200003];
int k,rez[200003];
void df(int i)
{
    nod[i].id=nod[i].low=++ID;
    nod[i].onstack=true;
    s.push(i);
    for(vector<int>::iterator j=v[i].begin();j!=v[i].end();j++)
    {
        if(nod[*j].id==UNVISITED)
            df(*j);
        if(nod[*j].onstack)
            nod[i].low=min(nod[i].low,nod[*j].low);
    }
    if(nod[i].low==nod[i].id)
    {
        int node;
        k++;
        do
        {
            node=s.top();
            s.pop();
            nod[node].onstack=false;
            rez[node]=k;
            if(nod[node].rez==-1)
            {
                nod[node].rez=1;
                nod[node^1].rez=0;
            }
        }while(node!=i);
    }
}
int n,m;
int main()
{
    ifstream f("2sat.in");
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        f>>a>>b;
        a= a<0? (-a)*2+1 : a*2;
        b= b<0? (-b)*2+1 : b*2;
        v[a^1].push_back(b);
        v[b^1].push_back(a);
    }
    ofstream g("2sat.out");
    bool exista=true;
    f.close();
    for(int i=2;i<=n*2+1;i++)
        if(nod[i].id==UNVISITED)
            df(i);

    for(int i=2;i<=n;i+=2)
        if(rez[i]==rez[i^1])
        {
            g<<-1;
            g.close();
            return 0;
        }
    for(int i=2;i<=n*2;i+=2)
        g<<nod[i].rez<<' ';
    g.close();
    return 0;
}