题目链接：http://poj.org/problem?id=2513
题意：给你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; }