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

算法：poj 3905 Perfect Election（2-SAT判断简单）2014-01-10 csdn shuangde800【思路】

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（）{inta, 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;}