POJ 3905

所属题类：图论中的2-SAT问题

题意：有N个人竞选某个职位，M个评委参与评选，每个评委给出一个条件，问能不能使得每个评委的条件都满足。若能，输出1，不能则输出0。

评委条件解释:

+i, +j 表示i或者j中至少有一个人竞选成功

-i, -j 表示i或者j中至少有一个落选

-i, +j 表示i落选或者j当选或者同时发生

+i, -j 表示i当选或者j落选或者同时发生

由此可得:

屏幕快照 2016-08-27 下午8.04.55.png

因此：在+i,+j的条件下

(i+n)一定能推出(j);
(j+n)一定能推出(i);
由此建立两条有向边, 其他条件则同理;

判断条件:

若同一个强联通分量中包含i和i+n这两个点，则表示i既当选和i既不当选，矛盾。此时无解

关于代码:

强联通分量的求解套用的是刘汝佳的入门经典训练指南scc的tarjacn算法.

#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

const int N = 1010 * 2;
vector<int> G[N];
stack <int> S;
int n, m, dfs_clock, scc_cnt;
int lowlink[N], pre[N], sccno[N];
bool flag;

void dfs(int u);
void find_scc();

int main ()
{
    while (scanf("%d %d", &n, &m) != EOF)
    {
        for (int i = 0; i < N; i++)
            G[i].clear();
        while (m-- != 0)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            if (a > 0 && b > 0)
            {
                G[b+n].push_back(a);
                G[a+n].push_back(b);
            }
            else if (a < 0 && b < 0)
            {
                G[-a].push_back(-b+n);
                G[-b].push_back(-a+n);
            }
            else if (a > 0 && b < 0)
            {
                G[a+n].push_back(-b+n);
                G[-b].push_back(a);
            }
            else if (a < 0 && b > 0)
            {
                G[-a].push_back(b);
                G[b+n].push_back(-a+n);
            }
        }
        find_scc();
        for (int i = 1; i <= n; i++)
        {
            if (sccno[i] == sccno[ i+n ])
            {
                flag = false;
                break;
            }
        }
        printf("%d\n", flag);
    }
    return 0;
}

void dfs(int u)
{
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for (int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if (!pre[v])
        {
            dfs(v);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        }
        else if (!sccno[v])
        {
            lowlink[u] = min(lowlink[u], pre[v]);
        }
    }
    if (lowlink[u] == pre[u])
    {
        scc_cnt++;
        while (true)
        {
            int x = S.top();
            S.pop();
            sccno[x] = scc_cnt;
            if (x == u) break;
        }
    }
}

void find_scc()
{
    dfs_clock = scc_cnt = 0;
    flag = true;
    memset(sccno, 0, sizeof(sccno));
    memset(pre, 0, sizeof(pre));
    for (int i = 1; i <= 2*n; i++)
    {
        if (!pre[i]) dfs(i);
    }
}