poj 3905 Perfect Election（2-SAT判断简单）

【题目链接】

http://poj.org/problem?id=3905

【思路】

2-SAT简单的判断题

【代码】

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 1010;
const int VN   = MAXN*2;
const int EN   = VN*VN*2;

int n, m;

 
struct Edge{
    int v, next;
};

struct Graph{
    int size, head[VN];
    Edge E[EN];
    void init(){size=0; memset(head, -1, sizeof(head)); };
    void addEdge(int u, int v){
        E[size].v = v;
        E[size].next = head[u];
        head[u] = size++;
    }
}g;

class Two_Sat{
public:
    bool check(const Graph& g, const int n){
        scc(g, 2*n);
        for(int i=0; i<n; ++i)
            if(belong[i] == belong[i+n])
                return false;
        return true;
    }
private:
    void tarjan(const Graph& g, const int u){
        int v; 
        low[u] = DFN[u] = ++idx;
        sta[top++] = u;
        instack[u] = true;

        for(int e=g.head[u]; e!=-1; e=g.E[e].next){
            v = g.E[e].v;
            if(DFN[v] == -1){
                tarjan(g, v);
                low[u] = min(low[u], low[v]);
            }else if(instack[v]){
                low[u] = min(low[u], DFN[v]);
            }
        }

        if(DFN[u] == low[u]){
            ++bcnt;
            do{
                v = sta[--top];
                instack[v] = false;
                belong[v]  = bcnt;
            }while(u != v);
        }
    }
    void scc(const Graph& g, const int n){
        bcnt = idx = top = 0;
        memset(DFN, -1, sizeof(DFN));
        memset(instack, 0, sizeof(instack));
        for(int i=0; i<n; ++i)
            if(DFN[i] == -1)
                tarjan(g, i);
    }
private:
    int idx, top, bcnt;
    int DFN[VN], low[VN], belong[VN], sta[VN];
    bool instack[VN];
}sat;

int main(){
    
    int  a, b;
    while(~scanf("%d%d", &n, &m)){

        g.init();
        for(int i=0; i<m; ++i){
            scanf("%d%d", &a, &b);

            if(a>0 && b>0){ // + +
                --a; --b;
                g.addEdge(a+n, b);
                g.addEdge(b+n, a);

            }else if(a>0 && b<0){ // + -
                b = -b;  
                --a; --b;
                g.addEdge(a+n, b+n);
                g.addEdge(b, a);

            }else if(a<0 && b>0){ // - +
                a = -a;
                --a; --b;
                g.addEdge(a, b); 
                g.addEdge(b+n, a+n);

            }else if(a<0 && b<0){// - -
                a = -a; b = -b;
                --a; --b;
                g.addEdge(a, b+n);
                g.addEdge(b, a+n);
            }
        }
        if(sat.check(g, n)) puts("1");
        else puts("0");
    
    }
    return 0;
}