题目

Description

You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?

Input

Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.

Output

If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.

Sample Input

blue red
red violet
cyan blue
blue magenta
magenta cyan

Sample Output

Possible



即木棍相接的颜色得相同~

本来想用哈希处理，WA了，提供从建议改用trie树，现在看来练习中难的够呛的算法也只不过是为了其他算法做配角再见

不仅仅说是并查集检验欧拉回路==trie树不也是嘛

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int total;
class trie
{
public:
    trie* next[26];
    char *color;
    int value; //标记这里是不是一个单词
    trie()
    {
        for(int i=0;i<26;i++)
            next[i]=0;
        color=NULL;
        value=-1;
    }
}root;
int insert(trie *p,char* s)
{

    int k=0;
    while(s[k]!='\0')
    {
        if(!p->next[s[k]-'a'])
            p->next[s[k]-'a']=new trie;
        p=p->next[s[k]-'a'];
        k++;
    }
    if(p->value==-1)
    p->value=(total++);
    return p->value;

    //在这里可根据具体题意来加东西
}
int a[500019];
int total1[500010],total2[500010];
int find(int x)
{
    if(x!=a[x]) a[x]=find(a[x]);
    return a[x];
}
void uni(int x,int y)
{
    x=find(x),y=find(y);
    if(x!=y) a[x]=y;
}
int main()
{
    //freopen("cin.txt","r",stdin);
    int t,n,sum;
    char str1[20],str2[20];
    trie *p=&root;
           // scanf("%d",&n);
          // memset(vis,false,sizeof(vis));
            for(int i=0;i<=500010;i++) a[i]=i;
            sum=0,total=0;
            int in=0,out=0;
            memset(total1,0,sizeof(total1));
            memset(total2,0,sizeof(total2));
            while(~scanf("%s%s",str1,str2))
            {
                int num1=insert(p,str1);
                int num2=insert(p,str2);
                total1[num1]++;//total2[num2]++;
                total1[num2]++;
                uni(num1,num2);
             //   printf("%d %d\n",num1,num2);
               // if(!vis[num1]){ total++;vis[num1]=true;}
               // if(!vis[num2]){ total++;vis[num2]=true;}
               //total=max(total,max(num1,num2));
            }
            for(int i=0;i<total;i++)
            {
                if(i==a[i]) sum++;
                /*if(total1[i]!=total2[i])
                {
                    if(total1[i]==total2[i]+1) in++;//cout<<i<<endl;
                    else if(total1[i]==total2[i]-1) out++;
                    else {sum+=100;break;}
                }*/
                if(total1[i]&1) in++;
                if(sum>1) break;
                if(in>2) break;
            }
           // if((sum==0||sum==1)&&((in==1&&out==1)||(in==0&&out==0)))printf("Possible\n");
             if((sum==0||sum==1)&&(in==0||in==2))
                  printf("Possible\n");
              else printf("Impossible\n");
          //  printf("sum=%d  in=%d  out=%d\n",sum,in,out);


    return 0;
}