Colored Sticks
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
题目大意：
给定一些木条，木条的两头都有颜色，颜色相同的两根木条可以相连，问是否可以连成一条直线。
解题思路：
其实就是问是否可以构成欧拉路径。这里给出欧拉路径的定义。
若图G中存在这样一条路径，使得它恰通过G中每条边一次,则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉(Euler)回路。（即一笔画问题）
存在欧拉路径的成分必要条件为：一个无向图存在欧拉回路，当且仅当该图只存在0或2个奇数入度数的顶点,且该图是连通图。
1)判断 奇数度数的个数
很好搞定，建立一个数组存放每个节点的入度，建图结束后遍历即可。
2)判断是否为连通图
使用并查集和路径压缩来做。若路径压缩之后每个点都有着相同的父节点（即每个点都有相同的祖先节点）。说明图连通。
Trie树的应用
由于该题的Node为字符串，建图的时候会比较困难。使用map映射会超时，所以使用Trie树来进行映射。具体实现请看代码备注。
Code:
/*************************************************************************
> File Name: poj2513.cpp
> Author: Enumz
> Mail: 369372123@qq.com
> Created Time: 2014年10月26日 星期日 20时16分17秒
************************************************************************/ #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<list>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#define MAXN 500001
using namespace std;
class TrieTree_Node
{
public:
bool flag; //判断是否为一个单词的叶子节点
int id; //为每一个单词分配一个id，相当于映射关系
TrieTree_Node *next[];
TrieTree_Node()
{
flag=;
id=;
memset(next,,sizeof(next));
}
}root;
int cnt=;
int degree[MAXN]; //入度数组
int father[MAXN];
int tree(char *s)
{
TrieTree_Node *p=&root;
int len=strlen(s);
for (int i=;i<=len-;i++)
{
int tmp=s[i]-'a';
if (p->next[tmp]==NULL)
p->next[tmp]=new TrieTree_Node;
p=p->next[tmp];
}
if (p->flag) //如果找到了该字符串，返回其ID
return p->id;
else //没有找到，就创建这个字符串，并标记叶子节点，分配ID
{
p->flag=;
p->id=++cnt;
return p->id;
}
}
int find(int a)
{
if (father[a]!=a)
father[a]=find(father[a]);
return father[a];
}
void join(int a,int b)
{
int fx=find(a),fy=find(b);
if (fx!=fy)
father[fx]=fy;
}
void init()
{
for (int i=;i<MAXN;i++) //并查集初始化，每一个节点相当于一棵树
father[i]=i;
}
int main()
{
char a[],b[];
init();
while (scanf("%s %s",a,b)!=EOF) //无向图，两个Node的入度都要加
{
int i=tree(a);
int j=tree(b);
degree[i]++;
degree[j]++;
join(i,j);
}
bool ok=;
int cnt_degree=;
for (int i=;i<=cnt;i++)
if (degree[i]%!=) cnt_degree++;
if (!(cnt_degree==||cnt_degree==))
ok=;
if (ok)
{
int tmp=find();
for (int i=;i<=cnt;i++)
{
if (tmp!=find(i))
ok=;
}
}
if (ok)
cout<<"Possible"<<endl;
else
cout<<"Impossible"<<endl;
return ;
}