题目大意：给定一捆木棒，每根木棒的每个端点涂有某种颜色。问：是否能将这些棒子首位项链，排成一条直线，且相邻两根棍子的连接处的颜色一样。
解题思路：此题是一道典型的判断欧拉回路或欧拉通路的问题，以木棍的端点颜色为顶点。方法是：先用并查集判断图是否连通，然后统计奇度顶点的个数sumj ， 如果 sumj == 0 , 则图中存在欧拉回路 ；如果 sumj == 2 ， 则图中存在欧拉通路 ； 如果 sumj > 2 ，则图中不存在欧拉通路。但是此题的关键是如何给端点颜色编号，一开始，我用map映射，结果TLE，所以，我就用到了Trie 树。
Ps：此题有坑！！当没有输入时，应当输出 Possible 。。
具体请看代码：
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std ;
const int MAXN = 3e6;
int set[MAXN] ;
char s1[100] ;
char s2[100] ;
int cnt ; // 给端点编号
int d[MAXN] ; // 统计每个顶点的度
struct Tnode
{
int du ;
int xu ;
Tnode *next[26] ;
Tnode()
{
du = 0 ;
xu = 0 ;
memset(next , 0 ,sizeof(next)) ;
}
} ;
int find(int x) // 并查集
{
int r = x ;
while (r != set[r])
{
r = set[r] ;
}
return r ;
}
int inse(char * str , Tnode * root)
{
Tnode *p = root ;
while (*str)
{
int id = *str - 'a' ;
if(p -> next[id] == NULL)
{
p -> next[id] = new Tnode ;
}
++ str ;
p = p -> next[id] ;
}
if(p -> du == 0)
{
p -> xu = ++ cnt ; // 顶点颜色的编号从 1 开始
}
p -> du ++ ;
d[p -> xu] = p -> du ;
return p -> xu ;
}
int main()
{
memset(d , 0 , sizeof(d)) ;
int i ;
for(i = 1 ; i <= MAXN ; i ++)
{
set[i] = i ;
}
cnt = 0 ;
Tnode *root = new Tnode ;
while (scanf("%s%s" , s1 , s2) != EOF)
{
int x = inse(s1 , root) ;
int y = inse(s2 , root) ;
int tx = find(x) ;
int ty = find(y) ;
if(tx < ty)
{
set[ty] = tx ;
}
else
{
set[tx] = ty ;
}
}
int fz = 0 ; // 判断图的连通的分支个数
int sumj = 0 ; // 统计奇度顶点的个数
for(i = 1 ; i <= cnt ; i ++)
{
if(set[i] == i)
{
fz ++ ;
}
if(d[i] % 2 == 1)
{
sumj ++ ;
}
}
if(cnt == 0)
{
puts("Possible") ;
}
else if(fz == 1)
{
if(sumj > 2)
{
puts("Impossible") ;
}
else
{
puts("Possible") ;
}
}
else
{
puts("Impossible") ;
}
return 0 ;
}