POJ 3905 Perfect Election 2-sat判断可行解

题目：

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

题意：

n个人参加选举，现在有个民意调查，有m个回复，每个回复有两个选择a b，如果a是正数，代表希望a当选，负数则希望-a不当选，两个选择至少满足一个，问有没有一个选举结果可以满足民意调查

思路：

建图很简单，只有OR的关系，不再说，具体看代码，跟lightoj有道题基本一样

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = ;
struct edge
{
    int to, next;
} g[N*N];
int cnt, head[N];
int num, idx, top, scc[N], st[N], dfn[N], low[N];
bool vis[N];
int n, m;
void add_edge(int v, int u)
{
    g[cnt].to = u, g[cnt].next = head[v], head[v] = cnt++;
}
void init()
{
    memset(head, -, sizeof head);
    memset(dfn, -, sizeof dfn);
    memset(vis, , sizeof vis);
    cnt = num = idx = top = ;
}
void tarjan(int v)
{
    dfn[v] = low[v] = ++idx;
    vis[v] = true, st[top++] = v;
    int u;
    for(int i = head[v]; i != -; i = g[i].next)
    {
        u = g[i].to;
        if(dfn[u] == -)
        {
            tarjan(u);
            low[v] = min(low[v], low[u]);
        }
        else if(vis[u]) low[v] = min(low[v], dfn[u]);
    }
    if(dfn[v] == low[v])
    {
        num++;
        do
        {
            u = st[--top], vis[u] = false, scc[u] = num;
        }
        while(u != v);
    }
}
int main()
{
    while(~ scanf("%d%d", &n, &m))
    {
        init();
        int a, b;
        for(int i = ; i <= m; i++)
        {
            scanf("%d%d", &a, &b);
            if(a >  && b > ) add_edge(a + n, b), add_edge(b + n, a);
            else if(a >  && b < ) add_edge(a + n, -b + n), add_edge(-b, a);
            else if(a <  && b > ) add_edge(-a, b), add_edge(b + n, -a + n);
            else add_edge(-a, -b + n), add_edge(-b, -a + n);
        }
        for(int i = ; i <=  * n; i++)
            if(dfn[i] == -) tarjan(i);
        bool flag = true;
        for(int i = ; i <= n; i++)
            if(scc[i] == scc[i+n])
            {
                flag = false; break;
            }
        if(flag) printf("1\n");
        else printf("0\n");
    }
    return ;
}