[原创]POJ 2513 Colored Sticks [tire树+并查集]

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

# define LL long long int
# define lalal puts("********");

const int N = 1010101;
const int Max = 26;
char s1[11],s2[11];
int pre[505050];
int degree[505050];
typedef struct node
{
    struct node *next[Max];
    int num;
    int index;
} Node;

//创建一个新节点
Node *createNew()
{
    Node *p=new Node;
    for(int i=0; i<Max; i++)
        p->next[i]=NULL;

    p->num=0;
    return p;
}

Node *head;
int ind=0;
//插入一个字符串
Node *Insert_str(char str[])
{
    int len=strlen(str);
    //  printf("len = %d--  ",len);
    Node *t,*p=head;
    for(int i=0; i<len; i++)
    {
        int c=str[i]-'a';
        if( p->next[c] == NULL )
        {
            //lalal
            t=createNew();
            p->next[c]=t;
        }
        p=p->next[c];
        //统计的时候要分清时机
        // cout<<p->num<<"-"<<str[i]<<" ";
    }
    p->num++;
    if(p->num==1)  p->index=++ind;
    return p;
}
int findi(int x)
{
    int r=x;
    while(r!=pre[r])
        r=pre[r];

    int i=x,j;
    while(i!=j)
    {
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}

void join(int x,int y)
{
    int fx=findi(x),fy=findi(y);
    if(fx!=fy)
        pre[fx]=fy;
}

void init()
{
    for(int i=0; i<=500050; i++)
    {
        pre[i]=i;
        degree[i]=0;
    }
    return ;
}

int main()
{
    head = createNew();
    init();
    int num=0;
    Node * tem1,*tem2 ;
    while(~scanf("%s %s",s1,s2))
    {
        tem1 = Insert_str(s1);
        tem2 = Insert_str(s1);

        degree[tem1->index]++;
        degree[tem2->index]++;

        join(tem1->index,tem2->index);
    }

    for(int i=1; i<=ind; i++)
    {
        if(degree[i]%2 == 1) num++;
        
        if(num>=3)
        {
            puts("Impossible");
            break;
        }
        
        if(findi(1)!=findi(i))
        {
            puts("Impossible");
            break;
        }
        
    }

    if(num!=1) puts("Possible");
    else     puts("Impossible");

    return 0;

}