POJ 2003 Hire and Fire：多重鏈表維護組織架構樹

問題描述

動態維護公司層級樹。操作：

• X hires Y：Y 成為 X 的直接下屬（加在子列表末尾，資歷最低）。
• fire X：移除 X。若 X 有下屬，資歷最高（最左）下屬遞補其位置（繼承資歷），遞補過程級聯向下直到葉子。
• print：先序遍歷輸出樹，縮進用 + 表示層級。

數據結構：多重鏈表

• 節點結構：name、父指針 fa、子指針鏈表 list son。
• map mp 映射姓名到節點指針，O(1) 查找。

關鍵操作實現

void Hire(string boss, string sub) {
    Tree* f = mp[boss];
    Tree* s = new Tree(); s->name = sub; s->fa = f;
    mp[sub] = s; f->son.push_back(s);
}
void Fire(string name) {
    Tree* cur = mp[name];
    // 級聯遞補：沿最左子鏈向下
    while (!cur->son.empty()) {
        Tree* child = cur->son.front();
        cur->name = child->name; // 繼承姓名（資歷）
        mp[cur->name] = cur;     // 更新映射
        cur = child;
    }
    // cur 現為葉子，從父鏈表移除並刪除
    mp.erase(name);
    cur->fa->son.remove(cur);
    delete cur;
}
void Print(int depth, Tree* u) {
    for(int i=0;iname << endl;
    for(auto v : u->son) Print(depth+1, v);
}

優勢

• 鏈表支持 O(1) 尾部插入、任意位置刪除（remove）。
• 映射表提供 O(1) 姓名定位。
• 遞補邏輯清晰：沿最左路徑向下複製姓名，最後刪除葉子。
• 輸出格式嚴格符合要求（60 個 - 分隔）。