POJ2513
本题题意是给一堆木棒，每种木棒左右两端有两种颜色，木棒进行拼接的时候，只有相同颜色之间才可以拼接，问最后是否可以将所有木棒拼为一根木棒。
我们考虑把同一种颜色的点聚在一起，我们就可以得到一个无向图，如果这个无向图是欧拉图，代表展开之后可以一笔走完，也就是可以连接成一条木棒。所以我们用trie树判断每种颜色出现的次数，再用并查集判一下图是否连通，最后用欧拉图的性质判断一下是否为欧拉图就好了（只存在两个或者0个奇度的点）
POJ2513代码
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<sstream>
using namespace std;
const int maxn =2e6+5;
int tree[maxn][30];
int sum[maxn];
int rank_[maxn];
int f[maxn];
int vis[maxn];
int flag,flag2;
int tot;
int cnt;
int pos1,pos2;
int insert_(char *str)
{int len=strlen(str);int root=0;for(int i=0;i<len;i++){int id=str[i]-'a';if(!tree[root][id]) tree[root][id]=++tot;root=tree[root][id];}if(!vis[root]) vis[root]=++cnt;if(f[cnt]==0) f[cnt]=cnt;//在这里重置f数组，节省一部分时间return vis[root];
}
int find_(int x){ return f[x]==x?x:f[x]=find_(f[x]);}
void union_(int x,int y)
{x=find_(x),y=find_(y);if(x!=y){if(rank_[x]>rank_[y]){f[y]=x;}else{f[x]=y;if(rank_[x]==rank_[y]) rank_[x]++;}}
}
char str1[12],str2[12];
int main()
{while(scanf("%s%s",str1,str2)!=EOF){pos1=insert_(str1);//统计该颜色对应的下标sum[pos1]++;pos2=insert_(str2);sum[pos2]++;//统计每种颜色的度union_(pos1,pos2);}for(int i=1;i<=cnt;i++){if(sum[i]%2==1){flag++;}if(find_(i)!=find_(1)){printf("Impossible\n");//非连通图return 0;}}if(flag==0||flag==2) printf("Possible\n");//欧拉图判定else printf("Impossible\n");return 0;
}