Codeforces Round #288 Div.2 D：Tanya and Password - 歐拉路徑詳解

題目重述

同 Codeforces 508D，給定 n 個三字符子串，還原長度 n+2 的原字符串。每個子串對應一條從前兩字符到後兩字符的有向邊，求歐拉路徑。

算法步驟

1. 節點編碼：將兩字符組合映射為整數 id = c1*62 + c2 (共 3844 個節點)。
2. 建圖：每個子串 s[0..2]，加邊 id(s[0],s[1]) → id(s[1],s[2])，記錄邊對應的子串索引。
3. 度數檢查：統計每節點出度 out、入度 in。必須滿足：所有節點 |out-in| ≤ 1，且 out-in=1 的節點數 = in-out=1 的節點數 ∈ {0,1}。
4. 連通性檢查：所有有邊節點在無向圖下連通（並查集或 DFS）。
5. Hierholzer DFS：從起點（若有 out=in+1 節點則為其，否則任意有邊節點）出發，DFS 遍歷所有邊，回溯時記錄節點。路徑逆序即為歐拉路徑。
6. 路徑驗證：路徑長度應為 n+1 個節點（對應 n 條邊），否則無解。
7. 輸出字符串：首節點輸出完整兩字符，後續節點各輸出最後一字符。

代碼關鍵片段

struct Edge { int to, nxt, id; } E[MAXE];
int head[MAXV], ecnt;
void addEdge(int u, int v, int id) { E[ecnt] = {v, head[u], id}; head[u] = ecnt++; }

vector path;
void dfs(int u) {
    for (int &i = head[u]; i != -1; i = E[i].nxt) {
        if (vis[i]) continue;
        vis[i] = 1;
        dfs(E[i].to);
    }
    path.push_back(u);
}

常見坑點

• 重邊處理：每條邊有唯一 id，vis 標記邊而非節點。
• 起點選擇錯誤導致路徑不完整。
• 字符映射錯誤（大小寫、數字順序）。
• 輸出時首節點需輸出兩字符，其餘各一字符。

總結

本題是歐拉路徑在字符串重構中的標準應用。掌握「子串→邊、重疊→節點」的建模技巧，並熟練實現 Hierholzer 算法（遞歸或棧模擬）是關鍵。