题意：
有很多棒子，两端有颜色，告诉你两端的颜色，让你把这些棒子拼接起来要求相邻的接点的两个颜色是一样的。
问能否拼接成功。
思路：
将颜色看作节点，将棒子看作边，寻找欧拉通路。
保证图的连通性的时候用到并查集。
这里颜色由于是字符串代替，所以需要用到字典树优化离散化过程。
字典树的学习感谢博客http://www.ahathinking.com/archives/14.html
重点是这个图很棒：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<iostream>
#include<stdlib.h>
using namespace std;
int me[*+];
int out[];
struct ti
{
void add(char *,int);
int findi(char *);
ti *mine[];
int num;
};
void ti::add(char *s,int tmp)
{
int len=strlen(s);
ti *next=this;
for(int i=;i<len;i++)
{
if(next->mine[s[i]-]==NULL)
{
next->mine[s[i]-]=(ti*)malloc(sizeof(ti));
memset(next->mine[s[i]-]->mine,NULL,sizeof(mine));
next->mine[s[i]-]->num=;
}
next=next->mine[s[i]-];
}
next->num=tmp;
}
int ti::findi(char *s)
{
int len=strlen(s);
ti *next=this;
for(int i=;i<len;i++)
{
if(next->mine[s[i]-]==NULL)
{
return ;
}
next=next->mine[s[i]-];
}
return next->num;
}
ti tree;
int findme(int n)
{
if(n!=me[n])
return me[n]=findme(me[n]);
return n;
}
int main()
{
memset(tree.mine,NULL,sizeof(tree.mine));
tree.num=;
char col1[],col2[];
for(int i=;i<=;i++)
{
me[i]=i;
}
int num=;
while(scanf("%s%s",col1,col2)!=EOF)
{
if(tree.findi(col1)==)
{
num++;
tree.add(col1,num);
}
if(tree.findi(col2)==)
{
num++;
tree.add(col2,num);
}
int tmpa=findme(tree.findi(col1));
int tmpb=findme(tree.findi(col2));
if(tmpa!=tmpb)
me[tmpb]=tmpa;
out[tree.findi(col1)]++;
out[tree.findi(col2)]++;
}
int c=;
int x,y,z;
x=y=z=;
for(int i=;i<=num;i++)
{
if(me[i]==i)
c++;
if(out[i]&)
x++;
}
if(x==||c>||x>)
printf("Impossible\n");
else
printf("Possible\n");
}