f292 - 11987 - Almost Union-Find
題目描述
題目要求實作一個類似於查並集 (Disjoint Set Union) 的資料結構，但增加了移除元素並加入另一個集合的功能。初始時，每個元素都屬於自己的集合。需要支援以下操作：
- 合併兩個集合。
- 將一個元素從其當前集合移除，並加入另一個集合。
- 查詢一個元素所屬集合的大小和元素總和。
解題思路
本題的核心是修改傳統的查並集資料結構以支援移除元素的操作。傳統的查並集僅支援合併集合和查找集合代表元素。為了支援移除操作，我們需要一個額外的機制來追蹤被移除的元素。
程式碼中，pm 是一個 map，用於儲存元素到其當前集合代表元素的映射。fa 陣列儲存每個元素的父節點，用於實現查找操作。sz 陣列儲存每個集合的大小，rk 陣列儲存每個集合中元素的總和。
對於移除操作，我們不會直接修改原始集合，而是將被移除的元素重新映射到一個新的集合，並更新其大小和總和。這樣可以避免修改原始集合的結構，保持查並集操作的效率。
具體來說，當執行移除操作時，我們將元素 x 從其原始集合中移除，並將其映射到一個新的集合 no++。然後，我們更新原始集合的大小和總和，並將新的集合的大小和總和初始化為 x。最後，我們將新的集合與目標集合 y 合併。
複雜度分析
- 時間複雜度: O(M * α(N))，其中 M 是操作次數，N 是元素的數量，α(N) 是反阿克曼函數，在實際應用中可以視為常數。
- 空間複雜度: O(N + M)，其中 N 是元素的數量，M 是新增集合的數量。
pmmap 最多會儲存 N + M 個元素。
程式碼
#include <iostream>
#include <map>
using namespace std;
map <long long,long long> pm;
long long fa[300005],sz[300005],rk[300005];
long long n,m,is,x,y,no;
long long ff(long long x){
if(fa[x]==x)return x;
return ff(fa[x]);
}
void un(long long x,long long y){
x=ff(x);
y=ff(y);
if(x==y)return;
if(sz[x]>sz[y]){
sz[x]+=sz[y];
rk[x]+=rk[y];
fa[y]=fa[x];
}
else{
sz[y]+=sz[x];
rk[y]+=rk[x];
fa[x]=fa[y];
}
}
int main(){
cin.tie(0); cout.tie(0);ios::sync_with_stdio(false);
while(cin >> n >> m){
pm.clear();
no=n+10;
for(int i=0;i<=n+m+5;++i){
if(i>n){
fa[i]=rk[i]=sz[i]=0;
}
else{
pm[i]=fa[i]=rk[i]=i;
sz[i]=1;
}
}
for(int i=0;i<m;++i){
cin >> is;
if(is==1){
cin >> x >> y;
x=pm[x];
y=pm[y];
un(x,y);
}
else if(is==2){
cin >> x >> y;
long long tx=pm[x];
long long ty=pm[y];
if(tx==ty)continue;
sz[ff(tx)]--;
rk[ff(tx)]-=x;
pm[x]=no++;
tx=pm[x];
sz[tx]=1;
rk[tx]=x;
fa[tx]=tx;
un(tx,pm[y]);
}
else{
cin >> x;
x=pm[x];
cout << sz[ff(x)] << " " << rk[ff(x)] << "\n";
}
}
}
}