:warning: 2-SAT
(graph_tree/two_sat.hpp)

Depends on

Code

#pragma once
#include<vector>
#include<algorithm>
#include"scc.hpp"
#include"graph_template.hpp"

/**
 * @brief 2-SAT
 */
struct two_sat{
    int n;
    graph v;
    std::vector<int>list;
    graph g;
    two_sat(int n):n(n){
        v.resize(n*2);
        list.resize(n*2,-1);
    }
    //add s==p&&t==q
    void add_edge(int s,int t,bool p,bool q){
        v[s+p*n].push_back(t+(1-q)*n);
        v[t+q*n].push_back(s+(1-p)*n);
    }
    bool solve(){
        static int scced=0;
        static bool ans=1;
        if(!scced){
            scced=1;
            tie(list,v)=scc(v);
            for(int i=0;i<n;i++){
                if(list[i]==list[i+n])ans=0;
            }
        }
        return ans;
    }
    bool operator[](int i){
        return list[i]>list[i+n];
    }
};
#line 2 "graph_tree/two_sat.hpp"
#include<vector>
#include<algorithm>
#line 3 "graph_tree/scc.hpp"
#include<tuple>
#line 4 "graph_tree/graph_template.hpp"
#include<iostream>
/**
 * @brief グラフテンプレート
 */

using graph=std::vector<std::vector<int>>;
template<typename T>
using graph_w=std::vector<std::vector<std::pair<int,T>>>;

graph load_graph(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;}
graph load_digraph(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);}return g;}
graph load_graph0(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;}
graph load_digraph0(int n,int m){graph g(n);for(int i=0;i<m;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);}return g;}
graph load_tree(int n){graph g(n);for(int i=0;i<n-1;++i){int s,t;std::cin>>s>>t;--s;--t;g[s].push_back(t);g[t].push_back(s);}return g;}
graph load_tree0(int n){graph g(n);for(int i=0;i<n-1;++i){int s,t;std::cin>>s>>t;g[s].push_back(t);g[t].push_back(s);}return g;}
graph load_treep(int n){graph g(n);for(int i=0;i<n-1;++i){int t;std::cin>>t;g[i+1].push_back(t);g[t].push_back(i+1);}return g;}
template<typename T>graph_w<T> load_graph_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;}
template<typename T>graph_w<T> load_digraph_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);}return g;}
template<typename T>graph_w<T> load_graph0_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;}
template<typename T>graph_w<T> load_digraph0_weight(int n,int m){graph_w<T> g(n);for(int i=0;i<m;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);}return g;}
template<typename T>graph_w<T> load_tree_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int s,t;T u;std::cin>>s>>t>>u;--s;--t;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;}
template<typename T>graph_w<T> load_tree0_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int s,t;T u;std::cin>>s>>t>>u;g[s].emplace_back(t,u);g[t].emplace_back(s,u);}return g;}
template<typename T>graph_w<T> load_treep_weight(int n){graph_w<T> g(n);for(int i=0;i<n-1;++i){int t;T u;std::cin>>t>>u;g[i+1].emplace_back(t,u);g[t].emplace_back(i+1,u);}return g;}
#line 6 "graph_tree/scc.hpp"

/**
 * @brief 強連結成分分解
 */

std::pair<std::vector<int>,graph> scc(const graph& g){
    int n=g.size();
    std::vector<std::vector<int>>rev(n);
    for(int i=0;i<n;i++)for(auto e:g[i]){
        rev[e].emplace_back(i);
    }
    int idx=0;
    std::vector<int>v(n,-1);
    std::vector<bool>visited(n,0);
    auto dfs=[&](auto dfs,int now)->void{
        visited[now]=1;
        for(auto e:g[now]){
            if(!visited[e])dfs(dfs,e);
        }
        v[idx++]=now;
    };
    for(int i=0;i<n;i++){
        if(!visited[i])dfs(dfs,i);
    }
    idx=-1;
    std::vector<int>res(n,-1);
    auto rdfs=[&](auto rdfs,int now)->void{
        for(auto e:rev[now]){
            if(res[e]==-1)res[e]=idx,rdfs(rdfs,e);
        }
    };
    for(int i=n-1;i>=0;--i){
        if(res[v[i]]==-1){
            res[v[i]]=++idx;
            rdfs(rdfs,v[i]);
        }
    }
    idx++;
    std::vector<std::vector<int>>res2(idx);
    for(int i=0;i<n;i++)for(auto e:g[i]){
        if(res[i]==res[e])continue;
        res2[res[i]].push_back(res[e]);
    }
    for(int i=0;i<idx;i++){
        std::sort(res2[i].begin(),res2[i].end());
        res2[i].erase(std::unique(res2[i].begin(),res2[i].end()),res2[i].end());
    }
    return {res,res2};
}
#line 6 "graph_tree/two_sat.hpp"

/**
 * @brief 2-SAT
 */
struct two_sat{
    int n;
    graph v;
    std::vector<int>list;
    graph g;
    two_sat(int n):n(n){
        v.resize(n*2);
        list.resize(n*2,-1);
    }
    //add s==p&&t==q
    void add_edge(int s,int t,bool p,bool q){
        v[s+p*n].push_back(t+(1-q)*n);
        v[t+q*n].push_back(s+(1-p)*n);
    }
    bool solve(){
        static int scced=0;
        static bool ans=1;
        if(!scced){
            scced=1;
            tie(list,v)=scc(v);
            for(int i=0;i<n;i++){
                if(list[i]==list[i+n])ans=0;
            }
        }
        return ans;
    }
    bool operator[](int i){
        return list[i]>list[i+n];
    }
};
Back to top page