poj 3678(2-SAT)

poj 3678

1、加边a->b 代表选了a的话b也得选
例如 x->x` 表示选了x就必须选x` ，所以这个值必为x
2、最好2*a表示True，2*a+1表示FLASE

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ms(i,j) memset(i, j, sizeof i);

const int MAXN = 1000 + 5;

struct TwoSAT
{
    vector<int> G[MAXN*2];
    int mark[MAXN*2];
    int S[MAXN*2];
    int n,c;
    void init(int n)
    {
        this->n = n;
        for (int i=0;i<=2*n;i++)
        {
            mark[i] = false;
            G[i].clear();
        }
    }
    void ins(int u, int v)
    {
        G[u].push_back(v);
    }
    int dfs(int x)
    {
        if (mark[x^1]) return false;
        if (mark[x]) return true;
        mark[x] = true;
        S[++c] = x;
        for (int i=0;i<G[x].size();i++)
        {
            if (!dfs(G[x][i])) return false;
        }
        return true;
    }
    int solve()
    {
        for (int i=0;i<2*n;i+=2)
        if (!mark[i]&&!mark[i+1])
        {
            c = 0;
            if (!dfs(i))
            {
                while (c>0) mark[S[c--]] = false;
                if (!dfs(i+1)) return false;
            }
        }
        return true;
    }
}ts;

int n,m;

void init()//x*2 is TRUE, x*2+1 is FALSE
{
    ts.init(n);
    for (int i=1;i<=m;i++)
    {
        int a,b,c,op = -1;
        char s[5];
        scanf("%d%d%d%s", &a, &b, &c, s);
        //op = 0 is OR, op = 1 is AND
        if (s[0]=='A')
            op = 1; 
        else if (s[0]=='O') op = 0;
        if (op==1)//AND
        {
            if (c)//1
            {
                ts.ins(a*2+1, a*2);
                ts.ins(b*2+1, b*2);
            } else//0
            {
                ts.ins(b*2, a*2+1);
                ts.ins(a*2, b*2+1);
            }
        } else if (op==0) //OR
        {
            if (c)//1
            {
                ts.ins(b*2+1, a*2);
                ts.ins(a*2+1, b*2);
            } else//0
            {
                ts.ins(a*2, a*2+1);
                ts.ins(b*2, b*2+1);
            }
        } else if (op==-1)
        {
            if (c)//1
            {
                ts.ins(a*2, b*2+1);
                ts.ins(a*2+1, b*2);
                ts.ins(b*2, a*2+1);
                ts.ins(b*2+1, a*2);
            } else//0
            {
                ts.ins(a*2, b*2);
                ts.ins(a*2+1, b*2+1);
                ts.ins(b*2, a*2);
                ts.ins(b*2+1, a*2+1);
            }
        }
    }
}
void solve()
{
    if (ts.solve()) printf("YES\n");
        else printf("NO\n");
}
int main()
{
    while (scanf("%d%d", &n, &m)==2)
    {
        init();
        solve();
    }
    return 0;
}