题意：给定一些木棒。木棒两端都涂上颜色，不同木棒相接的一边必须是
同样的颜色。求能否将木棒首尾相接。连成一条直线.
分析：能够用欧拉路的思想来解，将木棒的每一端都看成一个结点
由图论知识能够知道，无向图存在欧拉路的充要条件为：
① 图是连通的。
② 全部节点的度为偶数，或者有且仅仅有两个度为奇数的结点。
图的连通性能够用并查集，由于数据比較大，所以用并查集时要压缩路径，
全部节点的度（入度和出度的和）用数组记录就好
可是25w个木棒，有50w个结点，要怎么存呢，假设用数组，每次得查找，
效率特别低，这样就能够用trie树存储数据，用空间换取时间
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 500000
typedef struct stu
{
int id,flag; //id为结点的编号。flag标记改颜色是否存在
struct stu *next[26];
}node;
int num=1,f[M+5],d[M+5];
node* creat_node() //创建结点并初始化
{
node *p=(node*)malloc(sizeof(node));
p->id=p->flag=0;
memset(p->next,0,sizeof(p->next));
return p;
}
int trie_insert(node *p,char *s) //插入颜色结点。并返回其编号
{
int i;
while(*s!='\0'){
i=*s-'a';
if(p->next[i]==NULL)
p->next[i]=creat_node();
p=p->next[i];
s++;
}
if(!p->flag){
p->flag=1;
p->id=num++;
}
return p->id;
}
int find(int x) //并查集查找，并压缩路径
{
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
}
void mix(int a,int b) //并查集的合并
{
a=find(a);
b=find(b);
if(a!=b)
f[a]=b;
}
int main()
{
int i,j,n,m,flag=1;
node *root=NULL;
char s1[15],s2[15];
root=creat_node(); //创建根结点
for(i=1;i<=M;i++){ //父节点以及度的初始化
f[i]=i;
d[i]=0;
}
while(scanf("%s%s",s1,s2)!=EOF){
i=trie_insert(root,s1);
j=trie_insert(root,s2);
mix(i,j);
d[i]++;
d[j]++;
}
m=n=0;
for(i=1;i<num&&flag;i++){
if(d[i]%2)
n++; //记录度为奇数的结点
if(n>2)
flag=0;
if(f[i]==i) //记录公共祖先结点的个数
m++;
if(m>1)
flag=0;
}
if(flag)
printf("Possible\n");
else
printf("Impossible\n");
return 0;
}