POJ2513 Colored Sticks 字典树，欧拉回路

这题用map就超时了，所以用字典树来优化，第一次写静态的，现在都不习惯用指针了。

由于这里不要回到源点，所以不许要所有点的度都为偶数，零个或者两个均可，图也必须是连通的。

代码如下：

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <string>
using namespace std;

char s1[15], s2[15];
int idx = 0, flag = 0, ptr = 1;

int set[2500005];

struct Node
{
    int cnt, No;
    int ch[26];
}e[1250005];

int find(int x)
{
    return set[x] = x == set[x] ? x : find(set[x]);
}

int insert(int p, char *in)
{
    if (*in == '\0') {
        if (e[p].cnt == 0) {
            e[p].No = ptr++;
        }
        ++e[p].cnt;
        if (e[p].cnt & 1) {
            ++flag;
        }
        else {
            --flag;
        }
        return find(e[p].No);
    }
    else {
        if (e[p].ch[*in-'a'] == 0) {
            ++idx;
            e[p].ch[*in-'a'] = idx;
        }
        insert(e[p].ch[*in-'a'], in+1);
    }
}

int main()
{
    int x, y, root = 0;
    for (int i = 0; i <= 2500000; ++i) {
        set[i] = i;
    }
    while (scanf("%s %s", s1, s2) == 2) {
        x = insert(0, s1);
        y = insert(0, s2);
        if (x != y) {
            set[x] = y;
        }
    }
    for (int i = 1; i < ptr; ++i) {
        if (set[i] == i) {
            ++root;
        }
    }
    if (ptr == 1 || (flag == 0 || flag == 2) && root == 1) {
        puts("Possible");
    }
    else {
        puts("Impossible");
    }
    return 0;
}