更新中。
1. 扩展域并查集
扩展域并查集,就是将单个元素的 \(k\) 个状态拆成 \(k\) 个点进行维护的并查集。
例 \(1\):
现有 \(n\) 个元素,\(m\) 个二元关系,现在要将这些元素分成两个集合,使得每对二元关系对应的元素在不同的集合中。
问能否完成。
我们发现,每个元素都有 \(2\) 个状态(在 \(A/B\) 中),所以将第 \(i\) 个元素拆分成两个节点 \(i,n+i\),分别表示两个状态。
这样对于每个二元关系 \((i,j)\),必须满足 \(i\) 和 \(j\) 不在一个集合中,否则就不合法。
在合法的情况下,并将 \(i\) 和 \(j+n\) 所在集合合并。
例 \(2\)(P2024 [NOI2001] 食物链):
有 \(A,B,C\) 三种动物,其中 \(A\) 吃 \(B\),\(B\) 吃 \(C\),\(C\) 吃 \(A\)。每个动物都属于 \(A,B,C\) 中的一种。
现在有 \(k\) 句话,每句话形如“\(x\) 吃 \(y\)”或者“\(x\) 和 \(y\) 是同类”。若某句话和之前的真话冲突或者自相矛盾,则它是假话,否则是真话。
请统计有多少句假话。
首先我们需要将 \(x>n\) 或 \(y>n\) 的情况判掉。
接下来根据题意,我们考虑对每个元素 \(i\) 拆分出三个节点 \(i,i+n,i+2n\),分别表示 \(A,B,C\) 三个种类。
若 \(x\) 吃 \(y\),则根据定义:
- \(x\) 与 \(y+n\) 属于一个集合。
- \(x+n\) 与 \(y+2n\) 属于一个集合。
- \(x+2n\) 与 \(y\) 属于一个集合。
非法情况也容易判断,见代码。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,k,fa[N*3],ans;
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void merge(int x,int y){fa[find(x)]=find(y);}
signed main(){cin>>n>>k;for(int i=1;i<=3*n;i++) fa[i]=i;int t,x,y;while(k--){cin>>t>>x>>y;if(x>n||y>n) ans++;else if(t==1){if(find(x)==find(y+n)||find(x)==find(y+2*n)){ans++;}else{merge(x,y);merge(x+n,y+n);merge(x+2*n,y+2*n);}}else{if(find(x)==find(y)||find(x)==find(y+2*n)){ans++;}else{merge(x,y+n);merge(x+n,y+2*n);merge(x+2*n,y);}}}cout<<ans<<"\n";return 0;
}
例 \(3\)(CF776D The Door Problem):
给定 \(n\) 扇门,初始每扇状态为开或关。
有 \(m\) 个开关,每个开关可以控制若干扇门,按一下开关会让所有其控制的门状态反转。保证每扇门恰好被 \(2\) 个开关控制。
问能否开启所有的门。
将第 \(i\) 个开关拆分出两个节点 \(i,i+m\),对于第 \(i\) 扇门,记控制它的开关为 \(x,y\),则:
- 若 \(r_i=1\),则两个开关要么都按,要么都不按。即将 \(x,y\) 所在集合合并,将 \(x+m,y+m\) 所在集合合并。
- 若 \(r_i=0\),则两个开关必须恰好按其中一个。即将 \(x+m,y\) 所在集合合并,将 \(x,y+m\) 所在集合合并。
点击查看代码
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int N=1e5+5,M=1e5+5;
int n,m,fa[M<<1],r[N];
vector<int> a[N];
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void merge(int x,int y){fa[find(x)]=find(y);}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>r[i];for(int i=1;i<=2*m;i++) fa[i]=i;for(int i=1,x,y;i<=m;i++){cin>>x;while(x--) cin>>y,a[y].eb(i);}for(int i=1;i<=n;i++){if(r[i]){merge(a[i][0],a[i][1]);merge(a[i][0]+m,a[i][1]+m);}else{merge(a[i][0]+m,a[i][1]);merge(a[i][0],a[i][1]+m);}}for(int i=1;i<=m;i++){if(find(i)==find(i+m)) cout<<"NO",exit(0);}cout<<"YES";return 0;
}
2. 带权并查集
带权并查集,就是维护每个节点到自己根节点(路径压缩的话也就是 \(fa\))距离的并查集。
因为维护了边权,所以需要在路径压缩的时候对边权进行更新:
inline int find(int x){if(fa[x]==x) return x;int y=find(fa[x]);d[x]+=d[fa[x]];return fa[x]=y;
}
本节内容默认使用路径压缩,即 \(fa_x\) 既表示 \(x\) 所在子树的根,也表示 \(x\) 的父节点。
例 \(1\)(P2024 [NOI2001] 食物链)
题面见上。
我们考虑,\(p\) 与 \(q\) 两种动物的捕食关系,其实和 \(p,q\) 是哪种动物无关,它仅仅取决于 \(A\rightarrow B\rightarrow C\rightarrow A\) 这个三元环上,\(p\) 要走多少步才能到 \(q\)。
扩展域并查集的缺陷就在于它的实现思路是前者,需要将 \(p\) 所有 \(3\) 种状态的选择都分别于 \(q\) 进行合并。这样,若题目是 \(k\) 元环,时空复杂度都要额外乘上 \(k\),效率较低。
而带权并查集不依赖拆点,而是维护 \(p\) 到 \(fa_p\) 的边权(记为 \(d[p]\)),来表示 \(p\) 需要走多少步才能到 \(fa_p\)。不妨规定 \(d[p]\) 是模 \(3\) 意义下的。
对于 \(x\) 吃 \(y\),考虑如何合并 \(x,y\) 所在集合。
既然 \(x\) 吃 \(y\),那么 \(x\) 需要走 \(1\) 步到 \(y\)。
那么 \(fa_x\) 要走 \(d[y]-d[x]+1\) 步到 \(fa_y\)。
所以合并的时候,若将 \(fa_y\) 作为 \(fa_x\) 的父节点,则 \(d[fa_x]=d[y]-d[x]+1\)。
同理分析,若 \(x,y\) 是同类,则 \(d[fa_x]=d[y]-d[x]\)。
路径压缩同样要处理一下,即 \(d[x]\leftarrow d[x]+d[fa_x]\)。
这样就做完了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,k,fa[N],d[N],ans;
inline int find(int x){if(fa[x]==x) return x;int y=find(fa[x]);(d[x]+=d[fa[x]])%=3;return fa[x]=y;
}
inline bool merge(int x,int y,int w){find(x),find(y);//放在前面,因为需要d值(w+=d[y]-d[x]+3)%=3;x=fa[x],y=fa[y];if(x==y) return !w;fa[x]=y,d[x]=w;return 1;
}
signed main(){cin>>n>>k;for(int i=1;i<=n;i++) fa[i]=i;int t,x,y;while(k--){cin>>t>>x>>y;if(x>n||y>n) ans++;else ans+=!merge(x,y,t==1?0:1);}cout<<ans<<"\n";return 0;
}
\(k\) 元环的版本可以在 Library Checker 测试。
例 \(2\)(P1196 [NOI2002] 银河英雄传说):
现有 \(30000\) 个列和 \(30000\) 艘战舰,初始状态下第 \(i\) 列有第 \(i\) 艘战舰。
你要支持两种操作:
- 将第 \(i\) 列作为一个整体移至第 \(j\) 列的尾部。
- 判断战舰 \(i,j\) 是否在同一列;若在,求两者之间的战舰数量。
将战舰视作 \(n\) 个节点,初始均独立。
用 \(fa_i\) 表示当前列首,\(d[i]\) 表示 \(i\) 到 \(fa_i\) 的实际距离。
额外维护一个 \(siz_i\) 为子树 \(i\) 的大小,在 \(f_i\) 合并到 \(f_j\) 时,将 \(d[i]\) 累加 \(siz_j\)。
路径压缩和例 \(1\) 相同。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e4+5;
int t,x,y,fa[N],siz[N],d[N];
char op;
inline int find(int x){if(fa[x]==x) return x;int y=find(fa[x]);d[x]+=d[fa[x]];return fa[x]=y;
}
inline void merge(int x,int y){x=find(x),y=find(y);if(x^y) fa[x]=y,d[x]+=siz[y],siz[y]+=siz[x];
}
signed main(){cin>>t;for(int i=1;i<N;i++) fa[i]=i,siz[i]=1;while(t--){cin>>op>>x>>y;if(op=='M'){//合并 merge(x,y);}else{//查询if(find(x)^find(y)) cout<<"-1\n";else cout<<abs(d[x]-d[y])-1<<"\n";}}return 0;
}
双倍经验:P5092 [USACO04OPEN] Cube Stacking
例 \(3\)(P8779 [蓝桥杯 2022 省 A] 推导部分和):
现有一个序列,知道若干个区间的和,每次询问某个区间的和是否能确定;若能,输出该区间和。
前缀和一下,每个条件形如 \(S_r-S_{l-1}=s\)。
我们从 \(r\) 向 \(l-1\) 建一条权值为 \(s\) 的边,表示 \(l-1\) 的信息可以推出 \(r\) 的信息。并维护 \(d[x]\) 为 \(x\) 到根节点的距离。
和例 \(1\) 类似地,合并时若将 \(fa_y\) 作为 \(fa_x\) 的父节点,则有 \(d[fa_x]=d[y]-d[x]+s\)。
查询时,区间和可以推出,当且仅当若 \(l-1,r\) 在同一连通块。且此时的答案为 \(d[r]-d[l-1]\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,q,fa[N],d[N];
inline int find(int x){if(fa[x]==x) return x;int y=find(fa[x]);d[x]+=d[fa[x]];return fa[x]=y;
}
inline void merge(int x,int y,int w){int fx=find(x),fy=find(y);if(fx^fy) fa[fx]=fy,d[fx]=d[y]-d[x]+w;
}
signed main(){cin>>n>>m>>q;for(int i=1;i<=n;i++) fa[i]=i;int l,r,s;while(m--){cin>>l>>r>>s;merge(r,l-1,s);//注意顺序 }while(q--){cin>>l>>r;if(find(l-1)^find(r)) cout<<"UNKNOWN\n";else cout<<d[r]-d[l-1]<<"\n";}return 0;
}
3. 带删除并查集
带删除并查集,是支持将某个点独立出来的并查集,直接看例题。
例 \(1\)(SP5150 JMFILTER - Junk-Mail Filter):
现有 \(n\) 个元素,初始相互独立。
你要支持两种操作:
- 将两个元素所在集合合并。
- 将某个元素从所在集合中移出。
最后输出非空集合数量。
如果用普通的并查集,在移除 \(u\) 与 \(fa_u\) 的关系时,也会将 \(u\) 的后代一并移除。
要想解决这个问题,我们可以额外建 \(n+m\) 个虚点 \(n+1,n+2,\dots,2n+m\)。
所有合并操作都对虚点进行,真正的节点 \(1,2,\dots,n\) 只是挂在这些虚点上。这样分离的时候只需要将 \(fa_x\) 修改一下就可以了,不会改变原树结构。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e6;
int c,n,m,fa[2*N+M],idx;
set<int> s;//图省事直接用set了
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);char op;int x,y;while(cin>>n>>m){if(!n) break;s.clear();for(int i=1;i<=n;i++) fa[i]=n+i;for(int i=n+1;i<=2*n+m;i++) fa[i]=i;idx=2*n;while(m--){cin>>op;if(op=='M'){cin>>x>>y;fa[find(x+1)]=find(y+1); }else{cin>>x;fa[x+1]=++idx;}}for(int i=1;i<=n;i++) s.insert(find(i));cout<<"Case #"<<++c<<": "<<s.size()<<"\n";}return 0;
}
例 \(2\)(UVA11987 Almost Union-Find)
现有 \(n\) 个元素,初始相互独立。
你要支持三种操作:
- 将两个元素所在集合合并。
- 将一个元素移到另一个元素所在集合。
- 查询某元素所在集合的元素个数、元素和。
和例 \(1\) 的核心思想相同。所有操作都对虚点进行,所有信息也均存储在虚点。
真正的节点仅挂在这些虚点上,其指向只在操作二发生变化。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e5+5;
int n,m,fa[2*N],siz[2*N],sum[2*N];
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void merge(int x,int y){x=find(x),y=find(y);if(x^y) fa[x]=y,siz[y]+=siz[x],sum[y]+=sum[x];
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int k,p,q;while(cin>>n>>m){for(int i=1;i<=n;i++) fa[i]=i+n;for(int i=n+1;i<=2*n;i++) fa[i]=i,siz[i]=1,sum[i]=i-n;while(m--){cin>>k;if(k==1){cin>>p>>q;merge(find(p),find(q));}else if(k==2){cin>>p>>q;int pp=find(p),qq=find(q);siz[pp]--,siz[qq]++;sum[pp]-=p,sum[qq]+=p;fa[p]=qq;}else{cin>>p;cout<<siz[find(p)]<<" "<<sum[find(p)]<<"\n";}}}return 0;
}