并查集
并查集这个数据结构能很快的做到如下两个操作:
- 合并两个集合
- 查询每个结点的祖先节点
有两个优化:
- 路径优化
c++
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
- 按秩合并:优先将树高小的集合合并到树高大的集合(用的不多)
常用的几种思想:
- 记录每个集合的大小:绑定到根节点上
- 记录每个结点到根节点的距离:绑定到每个元素上
例1 1250. 格子游戏
题目描述
Alice和Bob玩了一个古老的游戏:首先画一个 n×n 的点阵(下图 n=3 )。
接着,他们两个轮流在相邻的点之间画上红边和蓝边:
直到围成一个封闭的圈(面积不必为 1)为止,“封圈”的那个人就是赢家。因为棋盘实在是太大了,他们的游戏实在是太长了!
他们甚至在游戏中都不知道谁赢得了游戏。
于是请你写一个程序,帮助他们计算他们是否结束了游戏?
输入格式
输入数据第一行为两个整数 n和 m。n表示点阵的大小, 表示一共画了 m 条线。
以后 m 行,每行首先有两个数字 (x,y),代表了画线的起点坐标,接着用空格隔开一个字符,假如字符是 D,则是向下连一条边,如果是 R 就是向右连一条边。
输入数据不会有重复的边且保证正确。
输出格式
输出一行:在第几步的时候结束。
假如 m 步之后也没有结束,则输出一行“draw”。
题目解析
题目看起来很复杂,其实读完之后就是要我们判断每次操作之后是否成功让图中形成一个封闭的图形,而想要形成一个封闭的图形,那么被连接的两个点一定处在同一个集合内。如果没有形成封闭图形,那么两个集合一定处在不同的集合内,因此我们可以用并查集来维护集合并进行集合的合并。
#include<bits/stdc++.h>
using namespace std;
const int N = 40010;
int p[N];
int n,m;
int get(int x,int y){
return x*n+y;
}
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main(){
cin>>n>>m;
int ans = 0;
for(int i=0;i<=n*n;i++) p[i] = i;
for(int i=1;i<=m;i++){
int x,y;
char op;
cin>>x>>y>>op;
x--,y--;
int a = get(x,y);
int b;
if(op == 'D') b = get(x+1,y);
else b = get(x,y+1);
int pa = find(a),pb = find(b);
if(pa == pb){
ans = i;
break;
}
p[pa] = pb;
}
if(!ans) puts("draw");
else cout<<ans<<endl;
return 0;
}
例2 1252. 搭配购买
题目描述
Joe觉得云朵很美,决定去山上的商店买一些云朵。
商店里有 n 朵云,云朵被编号为 1,2,…,n,并且每朵云都有一个价值。
但是商店老板跟他说,一些云朵要搭配来买才好,所以买一朵云则与这朵云有搭配的云都要买。
但是Joe的钱有限,所以他希望买的价值越多越好。
输入格式
第 11 行包含三个整数 n,m,w,表示有 n 朵云,m 个搭配,Joe有 w 的钱。
第 2∼n+1行,每行两个整数 $c_{i}$,$d_{i}$表示 i朵云的价钱和价值。
第 n+2∼n+1+m行,每行两个整数 $u_{i}$,$v_{i}$,表示买$u_{i}$就必须买 $v_{i}$,同理,如果买 $v_{i}$ 就必须买 $u_{i}$。
输出格式
一行,表示可以获得的最大价值。
题目解析
可以将每个捆绑销售的物品的集合看成一个物品,权重和价值都是集合中所有物品的和
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int p[N];
int v[N],w[N];
int dp[N];
int n,m,val;
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main(){
cin>>n>>m>>val;
for(int i=1;i<=n;i++){
p[i] = i;
cin>>v[i]>>w[i];
}
while(m--){
int a,b;
cin>>a>>b;
int pa = find(a),pb = find(b);
if(pa != pb){
v[pb] += v[pa];
w[pb] += w[pa];
p[pa] = pb;
}
}
for(int i=1;i<=n;i++){
if(p[i] != i) continue;
for(int j = val;j>=v[i];j--){
dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
}
}
cout<<dp[val];
return 0;
}
例3 237. 程序自动分析
题目描述
在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本:假设 x1,x2,x3,… 代表程序中出现的变量,给定 n 个形如 xi=xj 或 xi≠xj 的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。
例如,一个问题中的约束条件为:x1=x2,x2=x3,x3=x4,x1≠x4,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。
现在给出一些约束满足问题,请分别对它们进行判定。
输入格式
输入文件的第 1 行包含 1 个正整数 t,表示需要判定的问题个数,注意这些问题之间是相互独立的。
对于每个问题,包含若干行:
第 11 行包含 1 个正整数 n,表示该问题中需要被满足的约束条件个数。
接下来 n 行,每行包括 33 个整数 i,j,e,描述 11 个相等/不等的约束条件,相邻整数之间用单个空格隔开。若 e=1,则该约束条件为 xi=xj;若 e=0,则该约束条件为 xi≠xj。
题目解析
题目思路很简单,我们可以先把所有相等的约束处理掉(合并集合,在同一个集合表示相等),在依次处理每个不相等的约束,如果发现了不能满足的约束,也就是不等式两边的元素在同一个集合,判定为no,否则为yes
由于数据中约束的个数有$10^{5}$,而变量的下标却有$10^{9}$,所以我们可以对变量的下标做一个离散化,使其的范围缩小
解题代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 2e5+10;
int p[N];
unordered_map<int,int> mp;
int n,m,cnt;
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int hs(int x){
if(mp.count(x) == 0) mp[x] = ++cnt;
return mp[x];
}
int main(){
int T;
cin>>T;
while(T--){
cnt = 0;
mp.clear();
vector<PII> st;
cin>>n;
for(int i=1;i<=2*n;i++) p[i] = i;
for(int i=1;i<=n;i++){
int a,b,c;
cin>>a>>b>>c;
a = hs(a),b =hs(b);
if(c == 0){
st.push_back({a,b});
}else{
int pa = find(a),pb = find(b);
if(pa != pb) p[pa] = pb;
}
}
bool flag = true;
for(int i=0;i<st.size();i++){
int px = find(st[i].first);
int py = find(st[i].second);
if(px == py){
flag = false;
break;
}
}
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
例3 238. 银河英雄传说
题目描述
有一个划分为 N 列的星际战场,各列依次编号为 1,2,…,N。
有 N 艘战舰,也依次编号为 1,2,…,N,其中第 i号战舰处于第 i列。
有 T 条指令,每条指令格式为以下两种之一:
M i j
,表示让第 i 号战舰所在列的全部战舰保持原有顺序,接在第 j 号战舰所在列的尾部。C i j
,表示询问第 i 号战舰与第 j 号战舰当前是否处于同一列中,如果在同一列中,它们之间间隔了多少艘战舰。
现在需要你编写一个程序,处理一系列的指令。
输入格式
第一行包含整数 T,表示共有 T 条指令。
接下来 T 行,每行一个指令,指令有两种形式:M i j
或 C i j
。
其中 M 和 C 为大写字母表示指令类型,i 和 j 为整数,表示指令涉及的战舰编号。
输出格式
你的程序应当依次对输入的每一条指令进行分析和处理:
如果是 M i j
形式,则表示舰队排列发生了变化,你的程序要注意到这一点,但是不要输出任何信息;
如果是 C i j
形式,你的程序要输出一行,仅包含一个整数,表示在同一列上,第 i 号战舰与第 j 号战舰之间布置的战舰数目,如果第 i 号战舰与第 j 号战舰当前不在同一列上,则输出 −1。
题目解析
对于操作M:合并并查集的基本操作
对于操作C:想要查询i-j之间的战舰数量,首先判断是否在同一个并查集,如果不在,输出-1,如果在,则需要一个记录每个战舰到其排头(根节点)的距离,二者相减便可得到i-j之间的距离
因此我们需要维护一个数组来记录每个结点到其根节点的距离,由于每次find()函数结束之后,当前集合的所有结点的p[x]都会直接指向集合的根节点,因此我们只需要维护一个数组d[],其中d[x]表示x到p[x]的距离。
每次合并的时候,我们只需要将加入到队尾的集合的根节点的d[]更新成被加入集合的大小即可。
合并操作:
int pa = find(a),pb = find(b);
if(pa != pb){
d[pa] = sz[pb];
sz[pb] += sz[pa];
p[pa] = pb;
}
find()函数:
int find(int x){
if(x != p[x]){
int root = find(p[x]);
d[x] = d[x] + d[p[x]];
p[x] = root;
}
}
解题代码
#include<bits/stdc++.h>
using namespace std;
const int N = 30010;
int p[N],d[N],sz[N];
int find(int x){
if(x != p[x]){
int root = find(p[x]);
d[x] += d[p[x]];
p[x] = root;
}
return p[x];
}
int main(){
int T;
cin>>T;
for(int i=0;i<N;i++){
p[i] = i;
sz[i] = 1;
}
for(int i=0;i<T;i++){
char op;
int a,b;
cin>>op>>a>>b;
int pa = find(a),pb = find(b);
if(op == 'M'){
if(pa != pb){
d[pa] = sz[pb];
sz[pb] +=sz[pa];
p[pa] = pb;
}
}else{
if(pa != pb) puts("-1");
else{
cout<<max(0,abs(d[a]-d[b])-1)<<endl;
}
}
}
return 0;
}
例4 239. 奇偶游戏
题目描述
小 A 和小 B 在玩一个游戏。
首先,小 A 写了一个由 0 和 1 组成的序列 S,长度为 N。
然后,小 B 向小 A 提出了 M 个问题。
在每个问题中,小 B 指定两个数 l 和 r,小 A 回答 S[l∼r]中有奇数个 1 还是偶数个 1。
机智的小 B 发现小 A 有可能在撒谎。
例如,小 A 曾经回答过 S[1∼3]中有奇数个 1,S[4∼6] 中有偶数个 1,现在又回答 S[1∼6]] 中有偶数个 1,显然这是自相矛盾的。
请你帮助小 B 检查这 M 个答案,并指出在至少多少个回答之后可以确定小 A一定在撒谎。
即求出一个最小的 k,使得 01 序列 S 满足第 1∼k 个回答,但不满足第 1∼k+1 个回答。
输入格式
第一行包含一个整数 N,表示 01 序列长度。
第二行包含一个整数 M,表示问题数量。
接下来 M 行,每行包含一组问答:两个整数 l 和 r,以及回答 even
或 odd
,用以描述 S[l∼r] 中有偶数个 1 还是奇数个 1。
输出格式
输出一个整数 k,表示 01 序列满足第 1∼k 个回答,但不满足第 1∼k+1 个回答,如果 01 序列满足所有回答,则输出问题总数量。
题目解析
前缀和的思想
- 如果告诉我们L-R中有奇数个1(L R odd),则表示S[R]-S[L-1]为奇数,即S[R]与S[L-1]奇偶性不同
- 如果告诉我们L-R中有偶数个1(L R even),则表示S[R]-S[L-1]为偶数,即S[R]与S[L-1]奇偶性相同
带边权的并查集
记录d[x]表示x与p[x]的关系,如果d[x]等于0,表示同类,d[x]等于1表示不同类(这里的类别代表奇偶性)
-
如果告诉我们x与y是同类(奇偶性相同),px = find(x),判断px与py的关系:
-
if(px== py):表示x和y在同一个集合中,此时要进行判断(d[x]^d[y]),如果d[x]和d[y]表示的奇偶相同,则没有矛盾。如果d[x]和d[y]表示的奇偶性不同,则出现矛盾,直接break即可
-
if(px != py):表示x和y不在同一个集合,则进行集合的合并
c++ d[px] = d[x]^d[y];//表示如果d[x]和d[y]同类,则d[px]等于0 p[px] = py;
-
如果告诉我们x与y不是同类(奇偶性不同),px = find(x),判断px与py的关系:
-
if(px == py):表示x和y在同一个集合中,此时要进行判断(d[x] ^ d[y] ^ 1),如果d[x]和d[y]表示的奇偶相同,则出现矛盾。如果d[x]和d[y]表示的奇偶性不同,则没有矛盾
-
if(px != py):表示x和y不在同一个集合,则进行集合的合并
c++ d[px] = d[x]^d[y]^1;//表示如果d[x]和d[y]不同类,则d[px]等于0 p[px] = py;
解题代码
#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int p[N],d[N];
unordered_map<int,int> mp;
int n,m;
int get(int x){
if(mp.count(x) == 0) mp[x] = ++n;
return mp[x];
}
int find(int x){
if(x != p[x]){
int root = find(p[x]);
d[x] = d[x]^d[p[x]];
p[x] = root;
}
return p[x];
}
int main(){
cin>>n>>m;
n=0;
int res = m;
for(int i=0;i<N;i++) p[i] = i;
for(int i=1;i<=m;i++){
int a,b;
string s;
cin>>a>>b>>s;
a = get(a-1),b = get(b);
if(s == "even"){
int pa = find(a),pb = find(b);
if(pa == pb){
if(d[a]^d[b]){
res = i-1;
break;
}
}else{
d[pa] = d[a]^d[b];
p[pa] = pb;
}
}else{
int pa = find(a),pb = find(b);
if(pa == pb){
if(d[a]^d[b]) continue;
res = i-1;
break;
}else{
d[pa] = d[a]^d[b]^1;
p[pa] = pb;
}
}
}
cout<<res;
return 0;
}
带扩展域的并查集
这个方法的并查集中每一个元素存储的是一个命题,如果某一个集合中的一个命题成立了,则所有在这个集合中的命题都会成立。
本题中,我们用x表示命题x是奇数,x+BASE表示x是偶数
如果给定一个x y 同类,则需要判断一下x+BASE和y是否在同一个集合中,如果在,则break;如果不在,则合并集合
if(find(a+BASE) == find(b)){
res = i-1;
break;
}
//合并集合
p[find(a)] = find(b);
p[find(a+BASE)] = find(b+BASE);
如果给定x y 不同类,同上
程序代码
#include<bits/stdc++.h>
using namespace std;
const int N = 20010,BASE = N/2;
int p[N],d[N];
unordered_map<int,int> mp;
int n,m;
int get(int x){
if(mp.count(x) == 0) mp[x] = ++n;
return mp[x];
}
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main(){
cin>>n>>m;
n=0;
int res = m;
for(int i=0;i<N;i++) p[i] = i;
for(int i=1;i<=m;i++){
int a,b;
string s;
cin>>a>>b>>s;
a = get(a-1),b = get(b);
if(s == "even"){
if(find(a+BASE) == find(b)){
res = i-1;
break;
}
p[find(a)] = find(b);
p[find(a+BASE)] = find(b+BASE);
}else{
if(find(a) == find(b)){
res = i-1;
break;
}
p[find(a)] = find(b+BASE);
p[find(b)] = find(a+BASE);
}
}
cout<<res;
return 0;
}
江大是指的江南大学吗
是这样的