Twosat讲解详见算法入门经典1 324页

贴出白书模板

struct TwoSAT{
    int n;
    vector <int> G[maxn*2];
    bool mark[maxn*2];
    int S[maxn*2], c;
    bool dfs(int x){
        if(mark[x^1]) return false;
        if(mark[x]) return true;
        mark[x] = true;
        S[c++] = x;
        for(int i = 0; i < G[x].size(); i++){
            if(!dfs(G[x][i])) return false;
        }
        return true;
    }
    void init(int n){
        this->n = n;
        for(int i = 0; i < n*2; i++) G[i].clear();
        memset(mark, 0, sizeof(mark));
    }
    void addedge(int x, int xval, int y, int yval){
        x = x * 2 + xval;
        y = y * 2 + yval;
        G[x^1].push_back(y);
        G[y^1].push_back(x);
    }
    bool solve(){
        for(int i = 0; i < 2*n; i += 2)
        if(!mark[i] && !mark[i+1]){
            c = 0;
            if(!dfs(i)){//已经尝试过把i标记为true，然而不行，那么在尝试将i+1标记为真时，先把i的影响消掉
                while(c > 0) mark[S[--c]] = false;
                if(!dfs(i + 1)) return false;
            }
        }
        return true;
    }
}twosat;

例题推荐:

UVALIVE 3211 二分+TwoSAT

UVALIVE 3713 宇航员分组 TWOSAT

CF 766D TWOSAT http://blog.csdn.net/just_sort/article/details/60763945