题目链接：http://poj.org/problem?id=2513
思路很容易想到就是判断欧拉通路
预处理时用字典树将每个单词和数字对应即可
刚开始在并查集处理的时候出错了
代码：
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
int color;
#define maxn 26
#define MAX 500010
int parent[MAX];
int degree[MAX];
class Trie
{
public:
bool flag;
int id;
Trie *next[maxn];
};
Trie *root=new Trie;
void init()
{
memset(degree,,sizeof(degree));//存放各个点的度数
memset(parent,-,sizeof(parent));
Trie *q=root;//字典树初始化
for(int i=;i<maxn;i++)
q->next[i]=NULL;
q->flag=false;
q->id=;
}
/* 并查集构建并判断是否为连通图*/
int find(int x)
{
if(parent[x]==-) return x;
return parent[x]= find(parent[x]); } void Union(int u,int v)
{
int r1=find(u);
int r2=find(v); if(r1!=r2)
parent[r1]=r2;
}
int insert(char *s)
{
Trie *p =root; for(int i=; s[i]!='\0' ;i++)
{
int d=s[i]-'a'; if(p->next[d]==NULL)
{
Trie *temp=new Trie;
for(int j=;j<maxn;j++)
temp->next[j]=NULL;
temp->flag=;
temp->id=;
p->next[d]=temp;
}
p=p->next[d]; }
if(p->flag)
{
return p->id;
}
else
{
p->flag=;
p->id=color++;
return p->id;
} }
void del_trie(Trie * p)
{
for(int i=;i<maxn;i++)
if(p->next[i])
del_trie(p->next[i]); free(p);
}
int main()
{
char s1[],s2[];
init();
color=;
while(scanf("%s%s",s1,s2)!=EOF)
{
int num1=insert(s1);
int num2=insert(s2); degree[num1]++;
degree[num2]++;
Union(num1,num2); }
int cnt1=,cnt2=;
for(int i=;i<color;i++)//判断是佛否含欧拉通路
{
if(parent[i]==-) cnt1++;
if(degree[i]%==) cnt2++;
if(cnt1>) break;
if(cnt2>) break;
} if((cnt1== || cnt1==) &&(cnt2== || cnt2==))
printf("Possible\n");
else printf("Impossible\n");
// del_trie(root);
return ; }