gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 3678--Katu Puzzle
2-SAT 问题
关键：建图（建议先看赵爽的论文）
#include <stdio.h>
#include <cstring>
#include <stack>
using namespace std ;

const int MAXN = 2005 ;

struct Node{
    int ID; 
    Node *next;
}mapa[MAXN] ;

Node gTemp[110001] ;
int gPos = 0 ;


int N , M ;    //点数 边数
int g_Pred[MAXN], g_Num[MAXN], SN, flag[MAXN] ;
bool visited[MAXN];
stack<int> g_Stack ;

void Insert(int a, int b)
{ 
    Node *p = &gTemp[gPos++];
    p->ID = b;
    p->next = mapa[a].next;
    mapa[a].next = p;
}

void Build( const int& a , const int& b, const int& c, const char* cmd )
{
    if ( strcmp( cmd , "AND" ) == 0 )
    {
        if ( c == 1 )
        {
            Insert( a + N, a ) ;
            Insert( b + N, b ) ;
        }
        else {
            Insert( a, b + N ) ;
            Insert( b, a + N ) ;
        }
    }
    else if ( strcmp( cmd , "OR" ) == 0 )
    {
        if ( c == 1 )
        {
            Insert( a + N , b ) ;
            Insert( b + N , a ) ;
        }
        else {
            Insert( a, a + N ) ;
            Insert( b, b + N ) ;
        }
    }
    else if ( strcmp( cmd , "XOR" ) == 0 )
    {
        if ( c == 1 )
        {
            Insert( a + N , b ) ;
            Insert( b + N , a ) ;
            Insert( b , a + N ) ;
            Insert( a , b + N ) ;
        }
        else {
            Insert( a + N , b + N ) ;
            Insert( b + N , a + N ) ;
            Insert( a , b ) ;
            Insert( b , a ) ;
        }
    }
}

int MIN( const int& a, const int& b )
{
    return ( a < b ? a : b ) ;
}

// Tarjan算法 求SCC
void StrongDFS( int v )
{
    g_Pred[v] = g_Num[v] = SN++ ;

    g_Stack.push( v ) ;

    Node *ptr = mapa[v].next ;

    visited[v] = true ;

    while ( ptr ){
        if ( g_Num[ptr->ID] == 0 )
        {
            StrongDFS( ptr->ID ) ;
            g_Pred[v] = MIN( g_Pred[v], g_Pred[ptr->ID] ) ;
        }
        else if ( g_Num[ptr->ID] < g_Num[v] && !visited[ptr->ID] )
        {
            g_Pred[v] = MIN( g_Pred[v], g_Num[ptr->ID] ) ;
        }

        ptr = ptr->next ;
    }
    if ( g_Pred[v] == g_Num[v] )
    {
        int w = g_Stack.top() ;
        g_Stack.pop() ;
        while ( w != v )
        {
            flag[w] = SN ;
            w = g_Stack.top() ;
            g_Stack.pop() ;
        }
        flag[w] = SN ;
    }
}

void StronglyCon()
{
    int i ;

    memset(g_Num, 0, sizeof(g_Num)) ;
    memset(visited, 0, sizeof(visited)) ;
    memset(flag, 0, sizeof(flag)) ;
    SN = 1 ;

    for ( i = 0 ; i < N * 2 ; ++i )
    {
        if ( g_Num[i] == 0 )
            StrongDFS( i ) ;
    }
}



void Init()
{
    gPos = 0 ;

    int i ;

    for ( i = 0 ; i < MAXN ; ++i )
    {
        mapa[i].next = NULL ;
    }
    while ( !g_Stack.empty() )
    {
        g_Stack.pop() ;
    }
}


int main()
{
    int i , first , second , third ;
    char cmd[8] ;

    while ( scanf("%d %d", &N, &M) != EOF )
    {
        
        Init() ;

        for ( i = 0 ; i < M ; ++i )
        {
            scanf("%d %d %d %s", &first, &second, &third, &cmd) ;
            Build( first, second, third, cmd ) ;
        }

        StronglyCon() ;

        bool ans = true ;

        for ( i = 0 ; i < N ; ++i )
        {
            if ( flag[i] == flag[i + N] )
            {
                ans = false ;
                break ;
            }
        }

        if ( ans )
        {
            printf("YES\n") ;
        }
        else {
            printf("NO\n") ;
        }
    }
    return 0 ;
}
posted on 2008-10-30 23:26 巫 阅读(351) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理