当前位置: 首页 > news >正文

[笔记]并查集进阶(带权、扩展域、带删除)

更新中。

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;
}
http://www.hskmm.com/?act=detail&tid=31163

相关文章:

  • 20251013 模拟赛 总结
  • 什么是反应式编程 - 详解
  • SDL3和其附属的编译记录
  • Qwen多模态系列模型笔记—Qwen2-VL
  • WPF 调用 ChangeWindowMessageFilterEx 修改指定窗口 (UIPI) 消息筛选器的用户界面特权隔离
  • 实验1 现代C++基础课程
  • 牙科诊所借力AI营销4个月创收13万
  • 10月14日日记
  • P4653 [CEOI 2017] Sure Bet
  • 20251014
  • PHP虚拟主机测试页面
  • 歌词本。 - Slayer
  • 10月14日
  • 使用 Docker 快速搭建 MinIO 文件存储服务
  • 2025.10.14 正睿二十连测
  • singleton_pattern
  • ai出题
  • Python的Numpy、Pandas和Matplotlib(随笔)
  • 财务怎样做到业财融合 - 智慧园区
  • CF2146E
  • Spring Boot项目中集成Spring Security OAuth2和Apache Shiro
  • 【博客导航】
  • 部署向量数据库milvus
  • 从 0 到 1 实现高性能日志库 MiniSpdlog — 这可能是最适合新手的日志系统实战项目 !
  • 思想惰性:警惕时代中的精神惯性
  • journalctl 查看服务日志
  • 对ssh修改源码过程
  • 低代码时代,企业机遇在哪里
  • 2025 年浙江专升本培训学校推荐榜:浙江/台州/萧山/温州专升本机构,聚焦学历提升需求,杭州泓涵培训学校为学子护航
  • 25noip20d2t2 马戏表演 - Slayer