gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
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   知识库   博问   管理