UVA 12096 The SetStack Computer：STL 模擬集合棧

操作定義

• PUSH：壓入空集合
• DUP：複製棧頂
• UNION：彈出兩個集合，壓入並集
• INTERSECT：壓入交集
• ADD：將第一個集合作為元素加入第二個集合

每操作後輸出棧頂集合大小。

核心技巧：集合哈希映射

用 map<set<int>, int> 將每個不同集合映射為唯一整數 ID。ADD 操作實際是將第一個集合的 ID 作為元素插入第二個集合。

關鍵代碼

typedef set<int> sint;
map<sint, int> g;
stack<sint> stak;
int hn = 0;

void hashadd(sint u) { if (!g.count(u)) g[u] = hn++; }

void sf_add() {
    sint f = stak.top(); stak.pop();
    sint s = stak.top(); stak.pop();
    s.insert(g[f]);      // 關鍵：插入集合 f 的 ID
    hashadd(s); stak.push(s);
}

其餘操作直接用 STL set 的 insert、遍歷實現並集/交集。每操作結束輸出 stak.top().size()。