問題建模
n 根木棍，每根兩端有顏色（字符串）。相同顏色可連接。問能否將所有木棍首尾相連成單一鏈（歐拉路）。
圖論轉化
顏色作為頂點，木棍作為無向邊。問題等價於：無向圖是否存在歐拉路。
歐拉路存在條件（無向圖）
- 圖連通（非孤立頂點在同一連通分量）。
- 奇度頂點數為 0 或 2（0 為歐拉迴路，2 為歐拉路）。
算法流程
- 讀入所有木棍，將顏色字符串映射為整數 ID（哈希/映射）。
- 並查集維護連通性：每根木棍連接其兩端顏色 ID。
- 統計每個頂點度數（每根木棍兩端度數 +1）。
- 檢查：所有有邊頂點屬於同一並查集；奇度數 ≤ 2。
哈希優化關鍵
顏色字符串長度 ≤ 20，數量 ≤ 2n（n ≤ 200,000？題目未給上限但暗示大）。`std::map` 紅黑樹 O(log n) 可能超時。自定義哈希表：
- BKDR 哈希：`seed=131`，`hash = hash * seed + ch`，取模 `hashsize=1,000,007`（質數）。
- 開放定址法/鏈表法解決衝突。代碼中用 `hehe[]` 標記槽位是否佔用，`p[]` 存儲並查集父節點，`in[]` 存儲度數。
- 字符串查找/插入平均 O(1)，顯著加速。
代碼細節分析
提供代碼片段不完整（末尾截斷），但核心邏輯可見：
- `_hash(char*)` 計算哈希值。
- `_find(x)` 並查集路徑壓縮查找。
- 主循環讀入兩顏色，哈希獲取 ID，合併並查集，度數++。
- 最後遍歷哈希表檢查連通性（所有有邊點 `find` 同根）與奇度數。
複雜度
時間：O(n * L) 平均，L 為字符串長度。空間：O(n) 哈希表 + 並查集數組。
常見陷阱
- 孤立頂點（度數 0）不參與連通性檢查。
- 單根木棍：兩端點相同（自環），度數 +2，不影響奇偶性。
- 哈希衝突處理：代碼片段未展示完整衝突解決，實際需線性探測或鏈表。
總結
本題是歐拉路判定的經典應用，關鍵在於大規模字符串映射的哈希優化。掌握 BKDR 哈希、並查集、度數統計三大組件，可解決眾多圖論建模問題。
