文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
Trie树+并查集+欧拉通路
Description
You are given a bunch of wooden sticks. Each endpoint of each stick is colored with some color. Is it possible to align the sticks in a straight line such that the colors of the endpoints that touch are of the same color?
Input
Input is a sequence of lines, each line contains two words, separated by spaces, giving the colors of the endpoints of one stick. A word is a sequence of lowercase letters no longer than 10 characters. There is no more than 250000 sticks.
Output
If the sticks can be aligned in the desired way, output a single line saying Possible, otherwise output Impossible.
Sample Input
blue red
red violet
cyan blue
blue magenta
magenta cyan
Sample Output
Possible
Slyar:说下题目大意，给出n根木棍，每根木棍两端都有颜色，颜色为小于10的字符串，问能否将所有的木棍排成一排，使得每两根木棍衔接的地方颜色相同。
这题我一开始暴力做，很随意的就TLE了…看了Discuss发现要用什么”Trie”和”欧拉通路”，还要用到前几天学会的并查集…晕死，根本不知道什么是“Trie”和”欧拉通路”，遂Google了一下，得知“Trie”俗称字典树，具体内容完了发到博客上…欧拉通路完了也发博客上…本文发表2 weeks后应该可以搜索到…
对于知道以上概念者，可以看出本题就是将所有的颜色看做节点，连接两种颜色的木棍看做节点之间的连边，判断无向图中是否存在欧拉通路，判断条件是：
1、有且只有两个度为奇数的节点
2、图是连通的
由于节点是字符串，因此我们可以利用字典树将其转换成一个颜色序号。这样，统计每种颜色的出现次数就可以了。判断图是否连通，可以利用并查集：若最后所有节点在同一个集合，则图是连通的。
eg. blue (magenta magenta) (cyan cyan) (blue blue) (red red) violet
/*
PKU 2513
Slyar
//www.slyar.com/
*/
#include
#include
#define MAX 500001
/* father[x]表示x的父节点 */
int father[MAX];
/* rank[x]表示x的秩 */
int rank[MAX];
/* degree记录节点的度 */
int degree[MAX];
/* 记录字典树有效节点个数 */
int num = 0;
/* 定义字典树节点类型 */
typedef struct node
{
int key;
struct node *next[26];
}trie;
/* 创建根节点 */
trie *root;
/* 创建新节点 */
trie* New()
{
int i;
trie *p;
p = (trie*) malloc(sizeof(trie));
/* 初始化节点为未访问 */
p->key = -1;
/* 初始化孩子指针 */
for (i = 0; i < 26; i++)
{
p->next[i] = NULL;
}
return p;
}
/* 初始化 */
void Make_Set(int x)
{
father[x] = x;
rank[x] = 0;
degree[x] = 0;
}
/* 查找x元素所在的集合,回溯时压缩路径 */
int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]);
}
return father[x];
}
/* 合并x,y所在的集合 */
void Union(int x, int y)
{
if (x == y) return;
if (rank[x] > rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
}
/* 向以root为根的树中插入字符串s */
int Insert(trie *root, char *s)
{
int i;
trie *p = root;
for (i = 0; s[i] != '\0'; i++)
{
/* 节点若不存在则创建 */
if (p->next[s[i] - 'a'] == NULL)
{
p->next[s[i] - 'a'] = New();
}
/* 向下一层移动 */
p = p->next[s[i] - 'a'];
}
/* 得到并返回颜色节点序号 */
if (p->key == -1)
{
p->key = ++num;
}
return p->key;
}
/* 主函数 */
int main()
{
int i, x, y, sum;
char s1[11], s2[11];
/* 初始化集合 */
for (i = 0; i < MAX; i++)
{
Make_Set(i);
}
/* 初始化根节点 */
root = New();
/* 处理字符串 */
while(scanf("%s%s", s1, s2) != EOF)
{
/* 插入颜色，得到颜色节点序号 */
x = Insert(root, s1);
y = Insert(root, s2);
/* 更新颜色节点的度 */
degree[x]++;
degree[y]++;
/* 合并两根木棍 */
Union(Find_Set(x), Find_Set(y));
}
sum = 0;
/* 求度为奇数的点的个数 */
for (i = 1; i < num; i++)
{
if(degree[i] % 2) sum++;
}
/* 若度大于2则肯定不可能 */
if (sum > 2)
{
printf("Impossible\n");
}
/* 否则考察图是否连通 */
else
{
/* 考察所有的点是否在一个集合 */
for (i = 2; i < num; i++)
{
if (Find_Set(i) != Find_Set(1))
{
printf("Impossible\n");
return 0;
}
}
printf("Possible\n");
}
//system("pause");
return 0;
}
