POJ 3678 Katu Puzzle (2-SAT)

Katu Puzzle
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 5749
 
Accepted: 2077
Description
Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer c (0 ≤ c ≤ 1). One Katu is solvable if one can find each vertex Vi a value Xi (0 ≤ Xi ≤ 1) such that for each edge e(a, b) labeled by op and c, the following formula holds:
 Xa op Xb = c
The calculating rules are:
AND
0
일
0
0
0
일
0
일
OR
0
일
0
0
일
일
일
일
XOR
0
일
0
0
일
일
일
0
Given a Katu Puzzle, your task is to determine whether it is solvable.
Input
The first line contains two integers N (1 ≤ N ≤ 1000) and M,(0 ≤ M ≤ 1,000,000) indicating the number of vertices and edges.The following M lines contain three integers a (0 ≤ a < N), b(0 ≤ b < N), c and an operator op each, describing the edges.
Output
Output a line containing "YES"or "NO".
Sample Input

4 4

0 1 1 AND

1 2 1 OR

3 2 0 AND

3 0 0 XOR

Sample Output

YES

Hint
X
0 = 1,
X
1 = 1,
X
2 = 0,
X
3 = 1.
Source
POJ Founder Monthly Contest – 2008.07.27 , Dagger
 
 
비교적 간단한 2-SAT.
몇몇 표현식의 값을 주었는데, 이해가 있느냐고 물었다.
2-SAT로 판정하면 돼.

/*

POJ 3678

 AND,OR,XOR ， 

 2-SAT

*/

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<vector>

#include<queue>

#include<string.h>

using namespace std;



const int MAXN=2200;//



bool visit[MAXN];

queue<int>q1,q2;

//vector 

vector<vector<int> >adj; //     // '>' 

vector<vector<int> >radj;// 

vector<vector<int> >dag;// DAG 

int n,m,cnt;



int id[MAXN],order[MAXN],ind[MAXN];// ， ， 



void dfs(int u)

{

    visit[u]=true;

    int i,len=adj[u].size();

    for(i=0;i<len;i++)

      if(!visit[adj[u][i]])

        dfs(adj[u][i]);

    order[cnt++]=u;

}

void rdfs(int u)

{

    visit[u]=true;

    id[u]=cnt;

    int i,len=radj[u].size();

    for(i=0;i<len;i++)

      if(!visit[radj[u][i]])

        rdfs(radj[u][i]);

}

void korasaju()

{

    int i;

    memset(visit,false,sizeof(visit));

    for(cnt=0,i=0;i<2*n;i++)

      if(!visit[i])

        dfs(i);

    memset(id,0,sizeof(id));

    memset(visit,false,sizeof(visit));

    for(cnt=0,i=2*n-1;i>=0;i--)

      if(!visit[order[i]])

      {

          cnt++;// 

          rdfs(order[i]);

      }

}

bool solvable()

{

    for(int i=0;i<n;i++)

      if(id[2*i]==id[2*i+1])

        return false;

   return true;

}

int main()

{

    int a,b,c;

    char ch[10];

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        adj.assign(2*n,vector<int>());

        radj.assign(2*n,vector<int>());

        while(m--)

        {

            scanf("%d%d%d%s",&a,&b,&c,&ch);

            int i=a,j=b;

            if(strcmp(ch,"AND")==0)

            {

                if(c==1)// 1

                {

                    adj[2*i].push_back(2*i+1);

                    adj[2*j].push_back(2*j+1);

                    radj[2*i+1].push_back(2*i);

                    radj[2*j+1].push_back(2*j);

                }

                else // 1

                {

                    adj[2*i+1].push_back(2*j);

                    adj[2*j+1].push_back(2*i);

                    radj[2*j].push_back(2*i+1);

                    radj[2*i].push_back(2*j+1);

                }

            }

            else if(strcmp(ch,"OR")==0)

            {

                if(c==0)// 0

                {

                    adj[2*i+1].push_back(2*i);

                    adj[2*j+1].push_back(2*j);

                    radj[2*i].push_back(2*i+1);

                    radj[2*j].push_back(2*j+1);

                }

                else

                {

                    adj[2*i].push_back(2*j+1);

                    adj[2*j].push_back(2*i+1);

                    radj[2*j+1].push_back(2*i);

                    radj[2*i+1].push_back(2*j);

                }

            }

            else

            {

                if(c==0)// 

                {

                    adj[2*i].push_back(2*j);

                    adj[2*j].push_back(2*i);

                    adj[2*i+1].push_back(2*j+1);

                    adj[2*j+1].push_back(2*i+1);

                    radj[2*i].push_back(2*j);

                    radj[2*j].push_back(2*i);

                    radj[2*i+1].push_back(2*j+1);

                    radj[2*j+1].push_back(2*i+1);

                }

                else

                {

                    adj[2*i].push_back(2*j+1);

                    adj[2*j].push_back(2*i+1);

                    adj[2*i+1].push_back(2*j);

                    adj[2*j+1].push_back(2*i);

                    radj[2*i].push_back(2*j+1);

                    radj[2*j].push_back(2*i+1);

                    radj[2*i+1].push_back(2*j);

                    radj[2*j+1].push_back(2*i);

                }

            }

        }

        korasaju();

        if(solvable())printf("YES
");

        else printf("NO
");

    }

    return 0;

}