UVA 1556 Disk Tree：字典樹輸出目錄結構

題目大意

給定 N 個路徑（用 \ 分隔），按字典序輸出完整目錄樹，縮進表示層級。

字典樹構建

• 每個節點用 map 存儲子目錄名 → 子節點索引，自動有序。
• 插入路徑：按 \ 分割，逐層創建/查找節點。
• 遞歸輸出：按 map 順序遍歷，打印名稱並遞歸子節點（縮進 +1 空格）。

完整代碼

#include <cstdio>
#include <map>
#include <string>
#include <iostream>
using namespace std;
const int MAXN = 50005;
struct Trie {
    int sz;
    map g[MAXN];
    void init() { sz=1; g[0].clear(); }
    void insert(string s) {
        int u=0; string w;
        for (char c: s) {
            if (c=='\\') {
                if (!g[u].count(w)) { g[sz].clear(); g[u][w]=sz++; }
                u = g[u][w]; w.clear();
            } else w += c;
        }
    }
    void print(int u, int dep) {
        for (auto &kv: g[u]) {
            for (int i=0;i> n && n) {
        trie.init();
        for (int i=0;i> s; s += '\\'; trie.insert(s); }
        trie.print(0,0);
        cout << '\n';
    }
    return 0;
}

關鍵點

• map 自動按鍵排序，滿足字典序輸出要求。
• 路徑結尾加 \\ 確保最後一級目錄被處理。
• 節點數 ≤ 總路徑長度，MAXN=50005 足夠。