Codeforces 508D：Tanya and Password - 歐拉路徑構造密碼

問題描述

給定 n 個長度為 3 的子串（可能重複），它們是某長度為 n+2 字符串的所有連續三元子串。求還原出任意一個符合條件的原字符串，或判斷無解。

建模：有向圖歐拉路徑

• 每個兩字符組合（如 "ab"）作為一個節點。
• 每個三字符子串 "abc" 對應一條從 "ab" 到 "bc" 的有向邊。
• 原字符串對應一條遍歷所有邊恰好一次的路徑 —— 歐拉路徑。

歐拉路徑存在條件 (有向圖)

1. 圖在無向意義下連通（所有有邊節點在同一連通分量）。
2. 入度與出度滿足：要么所有節點 in == out（歐拉回路），要么恰有兩個節點 out = in + 1（起點）和 in = out + 1（終點），其餘 in == out。

構造路徑：Hierholzer 算法 (DFS 版)

void dfs(int u) {
    for (int &i = head[u]; i != -1; i = edges[i].next) {
        if (used[i]) continue;
        used[i] = true;
        dfs(edges[i].to);
    }
    path.push_back(u); // 回溯時記錄節點
}

• 用鏈式前向星存圖，head[u] 指向第一條邊。
• DFS 時修改 head[u] 跳過已用邊，避免重複遍歷。
• 路徑逆序即為歐拉路徑節點序列。

還原字符串

路徑節點序列 v0, v1, ..., vk (k = n+1)。每個節點代表兩字符。原串 = v0 的完整兩字符 + v1 最後一字符 + ... + vk 最後一字符。

完整代碼要點

• 字符映射：'0'-'9'→0-9, 'A'-'Z'→10-35, 'a'-'z'→36-61，共 62 字符，節點數 62*62 = 3844。
• 邊數 n ≤ 2e5，需靜態數組存儲。
• 判斷連通性：並查集或 DFS 遍歷有邊節點。

總結

經典「子串還原字符串」問題，建模為有向圖歐拉路徑。關鍵步驟：節點定義（長度-1 子串）、邊定義（長度 子串）、度數條件判斷、Hierholzer 算法構造路徑、路徑轉字符串。