gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
Pku 2513--Colored Sticks（Trie）
Trie + 并查集
#include <stdio.h>
#include <cstring>

const int MAXN = 600002 ;

int father[MAXN] ;
int degree[MAXN] ;
int N ;

int FindSet( int x )
{
    int t , y ;
    t = father[x] ;
    y = x ;
    while ( t != father[t] ) t = father[t] ;
    while ( x != t )
    {
        y = father[x] ;
        father[x] = t ;
        x = y ;
    }

    return t ;
}

void UnionSet( int x, int y )
{
    int u = FindSet(x) ;
    int v = FindSet(y) ;

    father[v] = u ;
}

const int CAP = 26 ;
typedef struct NODE
{    
    NODE()
    {
        cnt = 0;
        id = 0;
        memset(next, NULL, sizeof(NODE));
    };
    NODE *next[CAP];
    int cnt;
    int id;
}NODE;

const int MEMORY = 600001 ;//节点数目
NODE memory[MEMORY] ;
class BTree
{
public:
    BTree()
    {
        index = 1;
        id_index = 0;
        head = &memory[0];
    }

    //插入单词（返回单词ID）
    int insert(char *str)
    {
        int len = (int)strlen(str);
        NODE *pt = head;
        for (int i = 0; i < len; ++i)
        {
            if (pt->next[str[i]-'a'] == NULL)
            {
                pt->next[str[i]-'a'] = &memory[index++];
            }
            
            pt = pt->next[str[i]-'a'];
        }

        if (pt->cnt == 0)
            pt->id = id_index++;

        (pt->cnt)++;//单词累加一
        
        return pt->id;
    }

public:
    NODE *head;
    int index;//内存索引
    int id_index;//单词ID索引
};

void Init()
{
    int i ;

    for ( i = 0 ; i < MAXN ; i++ )
    {
        father[i] = i ;
        degree[i] = 0 ;
    }
}

int main()
{
    char str1[12], str2[12] ;
    BTree trie ;
    int x , y , num , i ;
    Init() ;
//    freopen("1.txt", "r", stdin) ;

    while ( scanf("%s %s", &str1, &str2) != EOF )
    {
        x = trie.insert( str1 ) ;
        y = trie.insert( str2 ) ;
        degree[x]++ ;
        degree[y]++ ;

        UnionSet( x, y ) ;
    }

    num = trie.id_index ;
    bool con = true ;

    if ( num == 0 ){
        printf("Possible\n") ;
    }
    else {
        
        x = FindSet( 0 ) ;
        
        for ( i = 1 ; i < num ; i++ )
        {
            y = FindSet( i ) ;
            if ( x != y )
            {
                con = false ;
                break ;
            }
        }

        if ( !con )
        {
            printf("Impossible\n") ;
        }
        else{
            x = 0 ;
            for ( i = 0 ; i < num ; i++ )
            {
                if ( degree[i] % 2 != 0 )
                    x++ ;
            }

            if ( x == 2 || x == 0 )
            {
                printf("Possible\n") ;
            }
            else{
                printf("Impossible\n") ;
            }
        }
    }


    return 0 ;
}
posted on 2008-11-08 15:50 巫 阅读(414) 评论(2)  编辑 收藏 引用 所属分类: 字符串处理

评论

# re: Pku 2513--Colored Sticks（Trie） 2009-02-11 17:20 LC
请问一下
pt->next[str[i]-'a'] = &memory[index++];

memory是用来保存什么啊
这句什么意思啊？
本人不太熟练指针有望指教啊！  回复  更多评论
  

# re: Pku 2513--Colored Sticks（Trie）[未登录] 2009-08-21 15:42 tom
memory 就一数组啊  回复  更多评论
  


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