所屬題類：圖論中的2-SAT問題

題意：有N個人競選某個職位袜炕，M個評委參與評選，每個評委給出一個條件初家，問能不能使得每個評委的條件都滿足偎窘。若能，輸出1溜在，不能則輸出0陌知。

評委條件解釋:

+i, +j 表示i或者j中至少有一個人競選成功

-i, -j 表示i或者j中至少有一個落選

-i, +j 表示i落選或者j當(dāng)選或者同時發(fā)生

+i, -j 表示i當(dāng)選或者j落選或者同時發(fā)生

由此可得:

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

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

(i+n)一定能推出(j);
(j+n)一定能推出(i);
由此建立兩條有向邊, 其他條件則同理;

判斷條件:

若同一個強聯(lián)通分量中包含i和i+n這兩個點，則表示i既當(dāng)選和i既不當(dāng)選掖肋，矛盾仆葡。此時無解

關(guān)于代碼:

強聯(lián)通分量的求解套用的是劉汝佳的入門經(jīng)典訓(xùn)練指南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);
    }
}