Cod sursa(job #3302752)

Utilizator andrei.nNemtisor Andrei andrei.n Data 10 iulie 2025 16:55:18
Problema 2SAT Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.6 kb
#include <bits/stdc++.h>

using namespace std;

namespace _2SAT
{
    vector<int> v1[200005];
    vector<int> v2[200005];
    int vis[200005];
    int ord[200005];
    int cnt;
    vector<int> comp[200005];
    int what[200005];

    #define v1 (v1+100002)
    #define v2 (v2+100002)
    #define vis (vis+100002)

    void dfs1(int node)
    {
        vis[node] = 1;
        for(auto &i : v1[node])
            if(!vis[i])
                dfs1(i);
        ord[++cnt] = node;
    }

    void dfs2(int node, int color)
    {
        vis[node] = color;
        for(auto &i : v2[node])
            if(!vis[i])
                dfs2(i, color);
    }

    vector<int> solve(int n, const vector<pair<int,int>> &edge)
    {
        for(const auto &i : edge)
        {
            v1[-i.first].push_back(i.second);
            v1[-i.second].push_back(i.first);
            v2[i.first].push_back(-i.second);
            v2[i.second].push_back(-i.first);
        }
        for(int i=-n; i<=n; ++i)
            if(i != 0 && !vis[i])
                dfs1(i);
        reverse(ord+1, ord+cnt+1);
        int color = 0;
        for(int i=1; i<=cnt; ++i)
            vis[ord[i]] = 0;
        for(int i=1; i<=cnt; ++i)
        {
            if(!vis[ord[i]])
                dfs2(ord[i], ++color);
            comp[vis[ord[i]]].push_back(ord[i]);
        }
        for(int i=1; i<=cnt; ++i)
            if(vis[ord[i]] == vis[-ord[i]])
                return vector<int>();
        for(int i=1; i<=color; ++i)
        {
            for(auto &node : comp[i])
            {
                for(auto &oth : v2[node])
                    if(what[vis[oth]])
                    {
                        what[i] = 1;
                        break;
                    }
                if(what[i]) break;
            }
            if(what[i]) continue;
            for(auto &node : comp[i])
                what[vis[-node]] = 1;
        }
        vector<int> ans(n+1);
        for(int i=1; i<=n; ++i)
            ans[i] = what[vis[i]];
        return ans;
    }

    #undef v1
    #undef v2
    #undef vis
}

signed main()
{
    ifstream fin ("2sat.in");
    ofstream fout ("2sat.out");
    ios::sync_with_stdio(false); fin.tie(0); fout.tie(0);
    int n, m; fin>>n>>m;
    vector<pair<int,int>> v;
    while(m--)
    {
        int a, b; fin>>a>>b;
        v.emplace_back(a, b);
    }
    const vector<int> &ans = _2SAT::solve(n, v);
    if(ans.empty())
    {
        fout<<"-1";
        return 0;
    }
    for(int i=1; i<=n; ++i)
        fout<<ans[i]<<' ';
    return 0;
}