图论——2-sat【借鉴】

借鉴：http://blog.csdn.net/chenzhenyu123456/article/details/47114535

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
struct edge
{
    int from,to,next;
}E[5000333];
vector <int> G[2222];
int tot;
int l1[3333];
int l2[3333];
int head[2222];
int low[2223];
int dfn[2222];
bool ins[2222];
int number[2222];
int color[2222];
int in[2222];
int scc_cnt;
int dfs_clock;
int fp[2222];
int N,M;
stack <int> S;
void addedge(int a,int b)
{
    E[tot].from = a;
    E[tot].to = b;
    E[tot].next = head[a];
    head[a] = tot++;
}
void init()
{
    memset(head,-1,sizeof(head));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(ins,0,sizeof(ins));
    memset(number,0,sizeof(number));
    memset(E,0,sizeof(E));
    memset(in,0,sizeof(in));
    memset(color,0,sizeof(color));
    memset(fp,0,sizeof(fp));
    for (int i = 0 ; i<= 2000 ; i++)
    G[i].clear();
    scc_cnt = 0;
    dfs_clock = 0;
    tot = 0;
    while (!S.empty()) S.pop();
}
void tarjan(int u)//求强连通
{
    int v;
    low[u] = dfn[u] = ++dfs_clock;
    S.push(u);
    ins[u] = true;
    for (int i = head[u] ; i != -1 ; i = E[i].next)
    {
        v = E[i].to;
        if (!dfn[v])
        {
            tarjan(v);

            low[u] = min(low[u],low[v]);
        }
        else if (ins[v])
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(low[u] == dfn[u])
    {
        scc_cnt++;
        for(;;)
        {
            v = S.top();
            S.pop();
            ins[v] = false;
            number[v] = scc_cnt;
            if(v == u) break;
        }
    }
}
void solve()
{
    for(int i = 1; i <= N; i++)
    {
        if(number[2*i] == number[2*i - 1])
        {
            //无解
            return ;
        }
        else
        {
            //拓扑排序的时候用到，对立面和自身不共存（对称性）
            fp[number[2*i]] = number[2*i - 1];
            fp[number[2*i - 1]] = number[2*i];
        }
    }
    //缩点建图
    for (int i = 0; i<tot ; i++)
    {
        int x = number[E[i].from];
        int y = number[E[i].to];
        if (x!=y)
        {
            G[y].push_back(x);
            in[x]++;
        }
    }
    //拓扑排序
    queue<int> Q;
    for(int i = 1; i <= scc_cnt; i++) if(in[i] == 0) Q.push(i);
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        if(color[u] == 0)
        {
            color[u] = 1;
            color[fp[u]] = 2;
        }
        for(int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i];
            if(--in[v] == 0)
            Q.push(v);
        }
    }
    //输出可行解
}
int main()
{
    while (1)//条件
    {
         init();
         //建立图
         for (int i = 1; i<=2 * N ;i++)
         {
             if (!dfn[i]) tarjan(i);
         }
         solve();
    }
}