欧拉回路专题 POJ - 2513字典树染色+并查集判连通

题目链接：http://poj.org/problem?id=2513
题目大意：

一些木棒，两端都涂上颜色，求是否能将木棒首尾相接，连成一条直线，要求不同木棒相接的一端必须是相同颜色的。

思路：

现在就是把颜色字符串抽象成点，用字典树进行染色就行了，当然如果图不连通的话，显然不成立，用并查集维护无向图的连通块就可以了，然后就是判断点的度数就行了。

#include <bits/stdc++.h>
using namespace std;

int cut;
int d[500010];
/***********并查集***********/

int a[500010];
int fd(int x)
{
    if(a[x]<0)
    {
        return x;
    }
    return a[x]=fd(a[x]);
}

int L(int x, int y)
{
    x=fd(x), y=fd(y);
    if(x!=y)
    {
        a[x]=y;
    }
}


/***************************/

/**********字典树***********/
struct Tree{
    bool vis;//标记
    int id;  //编号
    Tree *next[26];
    Tree()
    {
        vis=0;
        id=0;
        memset(next, 0, sizeof(next));
    }
};

int Insert(Tree *root, char *s)
{
    Tree *p=root;
    int i=0;
    while(s[i])
    {
        if(p->next[s[i]-'a']==NULL)//如果该位置 找不到 s[i]， 就开一个，指向它
        {
            Tree *t=new Tree();
            p->next[s[i]-'a']=t;
        }
        p=p->next[s[i]-'a'];//继续跑
        i++;
    }
    if(p->vis)//如果之前有过了，直接返回编号
    {
        return p->id;
    }
    else//之前没有，就先标记，然后赋值，返回值。
    {
        p->vis=true;
        p->id=cut++;//标记
        return p->id;
    }
}

void del(Tree *root)//删除字典树(多样例)
{
    for(int i=0;i<26;i++)
    {
        if(root->next[i]!=NULL)
        {
            del(root->next[i]);
        }
    }
    free(root);
}
/**********************/

/*******初始化*******/

void inio()
{
    memset(a, -1, sizeof(a));
    memset(d, 0, sizeof(d));
    cut=1;
}

/********************/

int main()
{
    //freopen("1.txt", "r", stdin);//文件读入
    inio();
    Tree *root=new Tree();
    char a[20], b[20];
    while(scanf("%s%s",a, b)!=EOF)
    {
        int x=Insert(root, a);
        int y=Insert(root, b);
        d[x]++, d[y]++;
        L(x, y);
    }
    int ans=0, flog=0;
    int T=fd(1);
    for(int i=1;i<cut;i++)
    {
        if(fd(i)!=T)
        {
            flog=1;
            break;
        }
        if(d[i]%2==1)
        {
            ans++;
        }
    }
    if(ans>2||flog)
    {
        printf("Impossible\n");
    }
    else
    {
        printf("Possible\n");
    }
    del(root);

    return 0;
}