Cod sursa(job #2593167)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 3 aprilie 2020 02:25:17
Problema 2SAT Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("2sat.in");
ofstream fout("2sat.out");

class TwoSat {
  private:
    int n;
    vector<vector<int>> adG, adT;
    vector<pair<int, int>> edges;

    inline int non(int x) {
        if (x > n)
            return x - n;
        return x + n;
    }

    void addEdge(int x, int y) {
        adG[x].push_back(y);
        adT[y].push_back(x);
        edges.emplace_back(x, y);
    }

    void dfsG(int node, vector<bool>& vis, vector<int>& topo) {
        vis[node] = true;
        for (int nghb : adG[node])
            if (!vis[nghb])
                dfsG(nghb, vis, topo);
        topo.push_back(node);
    }

    void dfsT(int node, vector<bool>& vis, vector<bool>& ans, bool& ok) {
        vis[node] = false;
        if (ans[node])
            ok = false;
        ans[non(node)] = true;
        for (int nghb : adT[node])
            if (vis[nghb])
                dfsT(nghb, vis, ans, ok);
    }

  public:
    TwoSat(int n) :
        n(n), adG(2 * n + 1), adT(2 * n + 1) { }

    void addProp(int x, int y) {
        if (x < 0) x = n - x;
        if (y < 0) y = n - y;
        addEdge(non(x), y);
        addEdge(non(y), x);
    }

    vector<bool> solve() {
        vector<bool> vis(2 * n + 1);
        vector<int> topo;
        for (int i = 1; i <= 2 * n; i++)
            if (!vis[i])
                dfsG(i, vis, topo);
        reverse(topo.begin(), topo.end());

        bool ok = true;
        vector<bool> ans(2 * n + 1);
        for (int node : topo)
            if (vis[node] && vis[non(node)])
                dfsT(node, vis, ans, ok);

        if (!ok)
            return vector<bool>();
        ans.resize(n + 1);
        return ans;
    }
};

int main() {
    int n, m; fin >> n >> m;
    TwoSat graph(n);
    for (int i = 0; i < m; i++) {
        int x, y; fin >> x >> y;
        graph.addProp(x, y);
    }

    auto ans = graph.solve();
    if (ans.empty())
        fout << -1;
    else
        for (int i = 1; i <= n; i++)
            fout << ans[i] << ' ';
    fout << '\n';

    fout.close();
    return 0;
}