POJ 2513-Colored Sticks （字典树）

题意：给你n个木棒，每个木棒两端各有一种颜色，两个木棒能连在一起当且仅当两个木棒有相同的一种颜色，问你这n个木棒能否连在一起。。

题解：首先需要判断能否构成欧拉回路，判断的方法很简单，判断每个木棒两端的的颜色出现多少次即可，假如有出现颜色的度为奇数次的话，只能出现两个，否则必不能构成欧拉回路，剩下的就是给每种颜色一个编号即可，字典树跑一发。

PS：这道题是去年就写过的题，只是想换种姿势搞一搞。。。。

#include<map>    
#include<stack>    
#include<queue>    
#include<vector>    
#include<math.h>    
#include<stdio.h>    
#include<iostream>    
#include<string.h>    
#include<stdlib.h>    
#include<algorithm>    
using namespace std;    
typedef long long  ll;    
#define inf 100000000000    
#define mod 1000000007     
#define  maxn  530010    
#define  lowbit(x) (x&-x)    
#define  eps 1e-10   
int degree[maxn],size=1,fa[maxn],cnt[maxn][27],vis[maxn],color;
char s1[20],s2[20];
int insert(char a[])
{
 int u=0,len=strlen(a),i;
 for(i=0;i<len;i++)
 {
  int v=a[i]-'a';
  if(!cnt[u][v])
  {
   vis[size]=0;
   cnt[u][v]=size++;
  }
  u=cnt[u][v];
 }
 if(!vis[u])
  vis[u]=++color;
 return vis[u];
}
int find(int x)
{
 if(fa[x]==x)
  return x;
 return fa[x]=find(fa[x]);
}
int main(void)
{
 int  i,ans=0;
 for(i=0;i<maxn;i++)
  fa[i]=i,degree[i]=0;
 while(scanf("%s%s",s1,s2)!=EOF)
 {
  int t1=insert(s1);
  int t2=insert(s2);
  degree[t1]++;degree[t2]++;
  int f1=find(t1),f2=find(t2);
  if(f1!=f2)
   fa[f1]=f2;
 }
 for(i=1;i<=color;i++)
 {
  if(degree[i]%2==1)
   ans++;
  if(ans>2 || find(1)!=find(i))
  {
   printf("Impossible\n");
   return 0;
  }
 }
 if(ans==1)
  printf("Impossible\n");
 else
  printf("Possible\n");
 return 0;
}