题目连接：uva 1556 - Disk Tree
题目大意：给出N个目录关系，然后按照字典序输出整个文件目录。
解题思路：以每个目录名作为字符建立一个字典树即可，每个节点的关系可以用map优化。
#include #include #include #include #include #include using namespace std; const int maxn = 50005; typedef map ::iterator iter; struct Tire { int sz; map g[maxn]; void init(); void insert(string s); void put(int u, int d); }tree; int main () { int n; string s; while (cin >> n && n) { tree.init(); for (int i = 0; i < n; i++) { cin >> s; s += '\\'; tree.insert(s); } tree.put(0, 0); cout << endl; } return 0; } void Tire::init() { sz = 1; g[0].clear(); } void Tire::insert(string s) { int u = 0; string word = ""; for (int i = 0; i < s.length(); i++) { if (s[i] == '\\') { if (!g[u].count(word)) { g[sz].clear(); g[u][word] = sz++; } u = g[u][word]; word = ""; } else word += s[i]; } } void Tire::put (int u, int d) { for (iter i = g[u].begin(); i != g[u].end(); i++) { for (int j = 0; j < d; j++) cout << " "; cout << i->first << endl; put(i->second, d + 1); } }