Colored Sticks POJ - 2513（trie树欧拉路）

题意：

　　就是无向图欧拉路

解析：

　　不能用map。。超时

　　在判断是否只有一个联通的时候，我比较喜欢用set，但也不能用set，会超时，反正不能用stl

emm

用trie树来编号就好了

#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <cctype>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#include <bitset>

#define rap(i, a, n) for(int i=a; i<=n; i++)

#define rep(i, a, n) for(int i=a; i<n; i++)

#define lap(i, a, n) for(int i=n; i>=a; i--)

#define lep(i, a, n) for(int i=n; i>a; i--)

#define rd(a) scanf("%d", &a)

#define rlld(a) scanf("%lld", &a)

#define rc(a) scanf("%c", &a)

#define rs(a) scanf("%s", a)

#define pd(a) printf("%d\n", a);

#define plld(a) printf("%lld\n", a);

#define pc(a) printf("%c\n", a);

#define ps(a) printf("%s\n", a);

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = , INF = 0x7fffffff, LL_INF = 0x7fffffffffffffff;

char str1[maxn], str2[maxn];

int rt, ans, tot;

int f[maxn], deg[maxn];

int trie[maxn << ][], vis[maxn << ];

//map<string, int> vis;

set<int> ss;

int find(int x)

{

    return f[x] == x ? x : (f[x] = find(f[x]));

}

void init()

{

    for(int i = ; i < maxn; i++) f[i] = i;

    tot = ans = ;

    mem(deg, );

}

int build(char* s)

{

    int len = strlen(s);

    rt = ;

    for(int i = ; i < len; i++)

    {

        int x = s[i] - 'a';

        if(trie[rt][x] == ) trie[rt][x] = ++tot;

        rt = trie[rt][x];

    }

    if(!vis[rt]) vis[rt] = ++ans;

    return vis[rt];

}

int main()

{

    init();

    int u, v;

    int cnt = ;

    while(scanf("%s%s", str1, str2) != EOF)

    {

        u = build(str1);

        v = build(str2);

        deg[u]++;

        deg[v]++;

        int l = find(u);

        int r = find(v);

        if(l != r) f[l] = r;

    }

    int ater = find();

    int flag = , cnt1 = , cnt2 = ;

    for(int i = ; i <= ans; i++)

    {

        int x = find(i);

        if(x != ater)

        {

            printf("Impossible\n");

            return ;

        }

        if(deg[i] & )

            cnt1++;

    }

    if(cnt1 ==  || cnt1 == )

        printf("Possible\n");

    else

        printf("Impossible\n");

    return ;

}