PKU2513-Colored Sticks

題目：http://poj.org/problem?id=2513
給出不超過250000根棍子
一根棍子用兩個字串(分別不超過10個字)來表示頭尾兩端的顏色
棍子可以反轉，問是否可能將棍子全部接成一條線、讓它們相接處顏色相同


程式碼：http://codepad.org/YXZxw7UM
我是從ACM訓練計畫的Trie點進來這題的
不過先看這題比較圖論的部分好了，我們可以把問題轉化成
各個不同的顏色就是不同的點，每根棍子就是連結兩個顏色的邊
原問題就等價於「是否有尤拉路徑存在」

想要尤拉路存在很簡單，辦到兩樣充要條件：(1)奇度點是2個或0個 (2)圖連通

(1)只要統計就可以，(2)則是依賴並查集

最有意思的來了，本題真正關鍵不是上面這兩樣！XD

而是怎麼把顏色字串轉成唯一的辨識數字

於是建造出字母樹Trie、每次讀顏色串進來都執行add_or_find，
Trie上沒有該顏色就發新的識別編號、不管有無都返回相應的顏色編號
(程式碼addorfind的功能)

然而Trie的空間需求肥得出名，以本題250000個棍子、500000個可能顏色來說…
需要開至少100萬個節點才夠

最後注意造樹的細節就能AC