算法小菜鸟今天在做byr论坛上大牛分类的基础算法题，就有这么一道题，被归类为trie。由于没有接触过trie，于是花了一上午时间研究trie。
再看这道题，还是没有思路，忍不住去discuss去看看，看完就受打击了：使用并查集判定欧拉通路。
我并查集也没有接触过，于是花了一下午去研究并查集，并解决了悬很久的kruscal求最小生成树问题，然后回忆图论中欧拉回路和欧拉通路的知识（google）。
（欧拉回路知识转自google）背景： 图论起源于18世纪，1736年瑞士数学家欧拉（Eular）发表了图论的第一篇论文“哥尼斯堡七桥问题”。在当时的哥尼斯堡城有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥联结起来，见图(1)。当时那里的居民热衷于一个难题：游人怎样不重复地走遍七桥，最后回到出发点。
为了解决这个问题，欧拉用ABCD四个字母代替陆地，作为4个顶点，将联结两块陆地的桥用相应的线段表示，如图(2)，于是哥尼斯堡七桥问题就变成了图(2)中，是否存在经过每条边一次且仅一次，经过所有的顶点的回路问题了。欧拉在论文中指出，这样的回路是不存在的。
1 定义
欧拉通路 (欧拉迹) ——通过图中每条边一次且仅一次，并且过每一顶点的通路。
欧拉回路 (欧拉闭迹) ——通过图中每条边一次且仅一次，并且过每一顶点的回路。
欧拉图 ——存在欧拉回路的图。
2 无向图是否具有欧拉通路或回路的判定
G有欧拉通路的充分必要条件为：G 连通，G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。
G有欧拉回路(G为欧拉图)：G连通，G中均为偶度顶点。
3 有向图是否具有欧拉通路或回路的判定
D有欧拉通路：D连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。
D有欧拉回路(D为欧拉图)：D连通，D中所有顶点的入度等于出度。
*********************************************************************************************
言归正传，晚上又来做这道题，结果AC了，也高兴不起来，花了一天的时间。但也学会了基本的trie，并查集使用。
这道题大意是：已知有n根木棒，每个木棒有两种颜色表示两端，问：能不能将所有的木棒连接成一条直线（连接处颜色相同）。
可以考虑无向图的欧拉通路问题：将每种颜色看成图中的一个节点，木棒看作连接节点的边，于是判断两点：
1，每种颜色（节点）的度
2，是否为连通图
首先，每种颜色的度可以通过每条木棒的两端颜色的累积得到，问题是，每种颜色都是字符串，怎么关联每种颜色和度呢？
最容易想到的是Hash，这肯定是可行的。例如degree [ hash(red) ]=5。表示颜色为红色的度为5。
但是，既然提示用trie树来做，那么trie树的节点的数据域就可以保存每种颜色的id（相当于分配的hash值，可以通过一个全局变量自增产生），这样经过将每种颜色字符串插入到tree中以后，通过trie树的search操作就能高效的获取每种颜色对应的id，没插入一种颜色，为其产生一个id，只需要注意相同颜色插入时的处理即可。
其次，判断无向图是否连通可以使用并查集来判定：经过n-1各union操作后，所有节点都在一个集合（树形结构表示集合的话，即所有节点的父节点（集合代表）都一样）。由于每种颜色是由字符串来标示的，每个集合保存颜色对应的唯一id。
通过上面两个步骤的判定，就可以得出结果。