POJ 2513 Colored Sticks (Trie树＋并查集＋欧拉路)

#include <cstdio>
#include <cstring>
int const MAX = 500005;
int fa[MAX], d[MAX], cnt;

struct Trie
{
    int sz, t[MAX][15];
    int jud[MAX];
    Trie()
    {
        sz = 1;
        memset(t[0], -1, sizeof(t));
        jud[0] = 0;
    }
    void clear()
    {
        sz = 1;
        memset(t[0], -1, sizeof(t));
        jud[0] = 0;
    }
    int idx(char c)
    {
        return c - 'a';
    }
    void insert(char* s, int v)
    {
        int u = 0, len = strlen(s);
        for(int i = 0; i < len; i++)
        {
            int c = idx(s[i]);
            if(t[u][c] == -1)
            {
                memset(t[sz], -1, sizeof(t[sz]));
                jud[sz] = 0;
                t[u][c] = sz++;
            }
            u = t[u][c];
        }
        jud[u] = v;
    }
    int search(char* s)
    {
        int u = 0, len = strlen(s);
        for(int i = 0; i < len; i++)
        {
            int c = idx(s[i]);
            if(t[u][c] == -1) 
                return -1;
            u = t[u][c];
        }
        if(jud[u]) 
            return jud[u];
        return -1;
    }
}t;


void Init()
{
    for(int i = 0; i < MAX; i++)
        fa[i] = i;
}

int Find(int x)
{
    return x == fa[x] ? x : fa[x] = Find(fa[x]);
}

void Union(int a, int b)
{
    int r1 = Find(a);
    int r2 = Find(b);
    if(r1 != r2)
        fa[r1] = r2;
}

bool eluer()
{
    int sum = 0, t = -1;
    for(int i = 1; i < cnt; i++)
        if(d[i] % 2) 
            sum++;
    if(sum != 0 && sum != 2)
        return false;
    for(int i = 1; i < cnt; i++)
    {
        if(t == -1)
            t = Find(i);
        else if(Find(i) != Find(t)) 
            return false;
    }
    return true;
}

int main()
{
    char s1[20],s2[20];
    cnt = 1;
    Init();
    t.clear();
    while(scanf("%s %s", s1, s2) != EOF)
    {
        if(t.search(s1) == -1)
            t.insert(s1, cnt++);
        int u = t.search(s1);
        if(t.search(s2) == -1)
            t.insert(s2, cnt++);
        int v = t.search(s2);
        Union(u, v);
        d[u]++;
        d[v]++;
    }
    if(eluer())
        printf("Possible\n");
    else
        printf("Impossible\n");
}