题目链接：
https://vjudge.net/problem/POJ-2513
题目大意：
给一些木棍，两端都有颜色，只有两根对应的端点颜色相同才能相接，问能不能把它们接成一根木棍
解题思路：
题意不难，典型的无向图判断是否存在欧拉通路或回路的问题。
1、欧拉通路或回路的判定条件是图联通，并且度数为奇数的点只有两个或者0个
2、颜色多，输入的字符串多，需要用字典树存储，给字符串标号用字典树标记
3、点数多，用并查集判断连通性。
第一次WA：没由开is_word标记，写成了前缀判断，此处应该是单词判断
第二次WA：判断连通的时候简单地用p[i] == i；满足该条件的数目等于1来判断连通性，但是此题输入的图可能很复杂，应该判断是否所有点的根节点是同一个点这样进行判断。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<algorithm>
#include<vector>
#include<sstream>
#define lowbot(i) (i&(-i))
using namespace std; const int maxn = 1e6 + ;
int tree[maxn][];
//字典树tree[u][v]表示编号为u的节点的下一个字母为v连接的节点的编号
int idx(char c){ return c - 'a'; }//可以写成宏定义
int tot = ;//根节点编号为1
bool is_word[maxn];
int sum[maxn];
int cnt = ;//cnt
int Insert(char s[], int u)//u表示根节点
//插入字符串s
{
for(int i = ; s[i]; i++)
{
int c = idx(s[i]);
if(!tree[u][c])
tree[u][c] = ++tot;
u = tree[u][c];
}
sum[u] = ++cnt;
is_word[u] = ;//标记单词结尾
return sum[u];
} int ID(char s[], int u)//返回单词s的编号
{
for(int i = ; s[i]; i++)
{
int c = idx(s[i]);
if(!tree[u][c])//还没有编号
return Insert(s, );
u = tree[u][c];
}
if(!is_word[u])//是前缀但是并不是单词
{
return Insert(s, );
}
return sum[u];
}
int p[maxn];//并查集
int d[maxn];//记录每个点度数之和
int Find(int x)
{
return x == p[x] ? x : p[x] = Find(p[x]);
}
int main()
{
for(int i = ; i < maxn; i++)
{
p[i] = i;
}
char s1[], s2[];
int u, v, x, y;
while(scanf("%s%s", s1, s2) != EOF)
{
u = ID(s1, );
v = ID(s2, );
//cout<<u<<" "<<v<<endl;
x = Find(u);
y = Find(v);
if(x != y)p[x] = y;
d[u]++;
d[v]++;
}
int flag = , flag1 = ;
//flag判断连通性
//flag1记录奇点度数的点的数目
int t = Find();
if(d[] & )flag1++;
for(int i = ; i <= cnt; i++)
{
if(Find(i) != t){flag = ;break;}
if(d[i] & )flag1++;
}
if(flag && (flag1 == || flag1 == ))
printf("Possible\n");
else printf("Impossible\n");
return ;
}