trie树+并查集

时间：2010-05-31 来源：buptstehc

题目来源：Colored Sticks
第一次写trie树，search函数查找字符串是否存在，不存在则创建相应结点，并输出字符串的编号。并查集的作用是判断最后生成的图示否是连通的。最后判断是否存在欧拉路径，利用欧拉图的性质判断图中所有顶点均有偶数个度或仅有两个顶点有奇数个度。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 250002
typedef struct node
{
    int data;
    struct node *next[26];
}node;
node *root;
int p[2 * SIZE], rank[2 * SIZE], degree[2 * SIZE], num = 1;

void makeSet(int x)
{
    p[x] = x;
    degree[x] = rank[x] = 0;
}

int findSet(int x)
{
    if(x != p[x])
        p[x] = findSet(p[x]);
    return p[x];
}

void unionSet(int x, int y)
{
    int px, py;

    px = findSet(x);
    py = findSet(y);

    if(px == py)
        return;

    if(rank[px] > rank[py])
        p[py] = px;

    else
    {
        p[px] = py;
        if(rank[px] == rank[py])
            rank[py]++;
    }
}

void init(void)
{
    int i;

    /*create root of trie tree.*/
    root = (node *)malloc(sizeof(node));
    memset(root, 0, sizeof(node));

    /*create initial disjoint-set.*/
    for(i = 1; i < SIZE; i++)
        makeSet(i);
}

int search(char *word)
{
    node *ptr = root;

    while(*word)
    {
        if(ptr->next[*word - 'a'] == 0)
        {
            ptr->next[*word - 'a'] = (node *)malloc(sizeof(node));
            memset(ptr->next[*word - 'a'], 0, sizeof(node));
        }

        ptr = ptr->next[*word - 'a'];
        word++;
    }

    if(ptr->data == 0)
        ptr->data = num++;

    return ptr->data;
}

int main(void)
{
    char s1[11], s2[11];
    int i, ss1, ss2, flag = 0, sum = 0;

    init();
    while(scanf("%s%s", s1, s2) != EOF)
    {
        ss1 = search(s1);
        ss2 = search(s2);

        unionSet(ss1, ss2);
        degree[ss1]++;
        degree[ss2]++;
    }

    /*check if graph is whole-linked.*/
    for(i = 2; i < num; i++)
    {
        if(p[1] != p[i])
        {
            flag = 1;
            break;
        }
    }

    if(!flag)
    {
        /*check if graph is Euler.*/
        for(i = 1; i < num; i++)
        {
            if((degree[i] % 2) == 1)
            {
                sum++;
                if(sum > 2)
                {
                    flag = 1;
                    break;
                }
            }
        }
    }

    if(flag)
        printf("Impossible\n");
    else
        printf("Possible\n");

    return 0;
}