冗余的代码

主要考查的是对并查集的运用，其次必须使用字典树，STL的map会超时。

模板题，不用动脑子。并查集判是否连通，欧拉回路判度数，字典树做map的工作。为了解题方便，特意写了个UFSets类。做完之后发现不用类的时间效率高出现在很多，大概主要时间都浪费在调用类函数上了……很多事都是这样，若是不仔细考虑，没有通盘规划，看上去与人方便，实际上平添事端。

/**//*
类调用函数效率不高，应直接用数组为宜
*/

#include <iostream>
#include <string>
using namespace std;

#define MAX 500001

// 并查集
class UFSets
{
private:
    int size;
    int *parent, *rank;
public:
    UFSets ();
    ~UFSets () { delete []parent; }
    void Union ( int root1, int root2 );
    int Find ( int x );
};
UFSets::UFSets ()
{
    size = MAX;
    parent = new int[size + 1];
    rank = new int[size + 1];
    int i;
    for ( i = 0; i <= size; i ++ )
        parent[i] = -1;
    for ( i = 0; i <= size; i ++ )
        rank[i] = 1;

}
int UFSets::Find ( int x )
{
    if ( parent[x] < 0 || parent[x] == x )
        return parent[x] = x;
    else
        return parent[x] = Find ( parent[x] );
}
void UFSets::Union ( int root1, int root2 )
{
    if ( rank[root1] < rank[root2] )
    {
        rank[root2] += rank[root1];
        parent[root1] = root2;
    }
    else
    {
        rank[root1] += rank[root2];
        parent[root2] = root1;
    }
}

// 字典树
struct TrieTree
{
    TrieTree *next[26];
    int id;
};
TrieTree *Root;

void init ()
{
    Root = new TrieTree;
    int i;
    for ( i = 0; i < 26; i ++ )
        Root->next[i] = NULL;
    Root->id = 0;
}

int search ( char s[] )
{
    int i, len = strlen ( s );
    TrieTree *p, *t;
    p = Root;
    for ( i = 0; i < len; i ++ )
    {
        if ( p->next[s[i] - 'a'] == NULL )
        {
            t = new TrieTree;
            int j;
            for ( j = 0; j < 26; j ++ )
                t->next[j] = NULL;
            t->id = 0;
            p->next[s[i] - 'a'] = t;
        }
        p = p->next[s[i] - 'a'];
    }
    if ( p->id == 0 )
        return p->id = cnt ++;
    else
        return p->id;
}

void del ( TrieTree *p )
{
    int i;
    for ( i = 0; i < 26; i ++ )
    {
        if ( p->next[i] != NULL )
            del ( p->next[i] );
    }
    delete p;
}


UFSets u;
char s1[100], s2[100];
int deg[MAX];
int cnt;

bool check1 ()
{
    int i, def = u.Find ( 1 );
    //printf ( "%d\n", def );
    for ( i = 2; i < cnt; i ++ )
    {
        //printf ( "%d\n", u.Find ( i ) );
        if ( u.Find ( i ) != def )
            return 0;
    }
    return 1;
}

bool check2 ()
{
    int i;
    int odd = 0;
    for ( i = 1; i < cnt; i ++ )
        if ( deg[i] & 1 )
            odd ++;
    return odd <= 2;
}

int main ()
{
    //freopen ( "in.txt", "r", stdin );
    //freopen ( "out.txt", "w", stdout );
    cnt = 1;
    memset ( deg, 0, sizeof ( deg ) );
    init ();
    while ( scanf ( "%s %s", s1, s2 ) != EOF )
    {        
        int i1 = search ( s1 ), i2 = search ( s2 );
        deg[i1] ++, deg[i2] ++;
        int r1 = u.Find ( i1 ), r2 = u.Find ( i2 );
        u.Union ( r1, r2 );
    }
    del ( Root );
    if ( !check1 () )
    {
        printf ( "Impossible\n" );
        return 0;
    }
    if ( !check2 () )
    {
        printf ( "Impossible\n" );
        return 0;
    }
    printf ( "Possible\n" );
    return 0;
}