【LDUOJ】寒假专题训练——并查集、种类并查集、带权并查集(参考题解)

深渊向深渊呼唤

写在前面: 希望大家把这篇题解作为参考题解,而不要去比着代码抄袭、作弊,做一些没有意义的事情。真正把并查集的原理搞懂才是此次训练的真正目的。

并查集专题训练题解

A. 亲戚 题目大意: 题目思路: Code: B.无所不在的宗教 题目大意: 题目思路: Code: C.星际争霸 题目大意: 题目思路: Code: D. 宇宙食物链 题目大意: 题目思路: Code: E. 超市 题目大意: 题目思路: Code: F. 奇偶博弈 题目大意: 题目思路: Code: G.天使与恶魔 题目大意: 题目思路: Code: 附言

A. 亲戚

题目大意:

给出一些亲戚的组合,亲戚关系具有传递性,将一些关系结合后,进行 p p p次询问,每次询问 x , y x,y x,y是否为亲戚

题目思路:

可以说是并查集的模板题

因为关系具有传递性,那么可以将这些人看作成一个个的点,亲戚关系作为一条一条的边。

那么对于每次询问,就转换为:判断两个点是否在同一个根树下。

用并查集就非常好的判断了,只会 f i n d ( ) find() find()函数即可。

Code:

/*** keep hungry and calm CoolGuang!  ***/
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn];
int Find(int x){
	return pre[x] == x?x:pre[x] = Find(pre[x]);
}
int main(){
	read(n);read(m);read(p);
	for(int i=1;i<=n;i++) pre[i] = i;
	for(int i=1;i<=m;i++){
		int x,y;read(x);read(y);
		int dx = Find(x),dy = Find(y);
		if(dx != dy) pre[dx] = dy;
	}
	
	for(int i=1;i<=p;i++){
		int x,y;read(x);read(y);
		if(Find(x) == Find(y)) puts("YES");
		else puts("NO");
	}
	return 0;

}

B.无所不在的宗教

题目大意:

每个学生都有自己的宗教信仰,已知 m m m对学生有相同的信仰,询问共有几个宗教?

题目思路:

将题意转换理解一下

a , b a,b a,b信仰相同, b , c b,c b,c信仰相同,那么 a , c a,c a,c信仰肯定也是相同的,也就是说 a , b , c a,b,c a,b,c是同一个宗教。所以把人看成点,相同关系看为边,那么就是求这个图中有多少个连通块,同一个连通块内信仰相同。

连通块:连通块内任何两点都可达

联通块的问题,可以用并查集去求解:因为(路径压缩)并查集的本质是将所有的点压缩到一个根下,那么假设有一个根 r t rt rt,那么所有的组先是 r t rt rt的节点,都是该连通块内的点,所以只需要判断有几个根即可

Code:

/*** keep hungry and calm CoolGuang!  ***/
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn];
int Find(int x){
	return pre[x] == x?x:pre[x] = Find(pre[x]);
}
int main(){
	int cas = 0;
	while(~scanf("%lld%lld",&n,&m)){
		if(n == 0 && m==0) break;
		for(int i=1;i<=n;i++) pre[i] = i;
		for(int i=1;i<=m;i++){
			int x,y;read(x);read(y);
			int dx = Find(x),dy = Find(y);
			if(dx != dy) pre[dx] = dy;
		}
		int ans = 0;
		for(int i=1;i<=n;i++)
			if(pre[i] == i) 
				ans++;
		printf("Case %d: %d\n",++cas,ans);
	}
	return 0;

}
`----------------------------------难度加大分割线------------------------------------------`

C.星际争霸

题目大意:

给出 T T T条指令,初始时,所有战舰所在的行均不相同,进行两种操作:

M   i   j M\ i\ j M i j 将 i i i 所在的行 连接到 j j j所在行的后面 C   i   j C\ i\ j C i j 如果 i i i, j j j在同一行输出它们两个相距几个战舰,否则输出-1

题目思路:

带权并查集

因为普通并查集已经维护不了相距几个战舰的操作,所以此时需要把路径压缩时的边附加一个权值

所以此时需要新开一个数组 r k [ i ] rk[i] rk[i], r k [ i ] rk[i] rk[i]代表i节点对于当前所处的连通块根节点的排名。例如: 3 − > 2 − > 1 3->2->1 3−>2−>1,那么 1 1 1在该连通块内排名第 1 1 1, 2 2 2排名第 2 2 2

如果此时需要将第 x x x个连通块与第 y y y个连通块进行合并,并以 y y y为根,那么y连通块内所有点对于根的排名是不需要改变的。但是 x x x连通块内的排名是需要改变的,但是又不能全改(时间不允许)。所以现在假设:

x x x联通块的根为 d x dx dx, y y y连通块的根为 d y dy dy。

已知 r k [ x ] rk[x] rk[x]与 r k [ d x ] rk[dx] rk[dx]的大小关系, r k [ d x ] rk[dx] rk[dx]与 r k [ d y ] rk[dy] rk[dy]大小的关系,合并之后 d x dx dx的排名肯定为y连通块内数量 + 1 +1 +1

那么x与dy的关系肯定也可以推出来的:
d x − x = a , d y − d x = b dx - x = a , dy - dx = b dx−x=a,dy−dx=b,那么 d y − x = a + b dy - x = a+b dy−x=a+b,所以 x x x与 d y dy dy的关系也就知道了合并就好了。

Code:

/*** keep hungry and calm CoolGuang!  ***/
/*#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)*/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn],sz[maxn];
int rt[maxn],rk[maxn];
int Find(int x){
	if(pre[x] == x) return x;
	int t = pre[x];
	pre[x] = Find(pre[x]);
	rk[x] += rk[t];
	return pre[x];
}
int main(){
	read(n);
	for(int i=1;i<=500000;i++) pre[i] = i,sz[i] = 1;
	for(int i=1;i<=n;i++){
		char op[5];
		int x,y;
		scanf("%s%d%d",op,&x,&y);
		if(op[0] == 'M'){
			int dx = Find(x),dy = Find(y);
			pre[dx] = dy;
			rk[dx] = sz[dy];
			sz[dy]  += sz[dx];
		}else{
			int dx = Find(x),dy = Find(y);
			if(dx != dy) printf("-1\n");
			else printf("%d\n",abs(rk[x]-rk[y])-1);
		}
	}
	return 0;

}

D. 宇宙食物链

题目大意:

有一些动物,存在两种关系:

X X X吃 Y Y Y, X X X也可以吃掉 Y Y Y的同类 X X X与 Y Y Y是同类, X X X可以吃 Y Y Y的猎物, Y Y Y可以吃 X X X的猎物。

然后给出一些食物关系(按顺序),你需要按顺序判断每次给出关系是否合法,不合法就抛弃并计数,否则就将加入到食物链中

题目思路:

这题也可以带权并查集求解,但是上面题目带权了之后,这个题目就不想再写同样的类型。

这里附带种类并查集的做法:

对于一个动物来说,有三种集合:

自己的同类 自己的猎物 自己的天敌(吃自己的)

对于一个动物,就可以用 i i i, i + n i+n i+n, i + 2 ∗ n i+2*n i+2∗n去表示。

所以对于同类关系$(a,b)$的判断:

1.首先判断是否冲突,也就是说是否存在 a a a吃 b b b 或者 b b b吃 a a a 的现象

2.由于种类并查集所以只需要知道 a a a的猎物 和 b b b的天敌是否属于同一集合,或者 b b b的猎物 和 a a a的天敌是否属于同一集合。这样可以用并查集轻松解决。

3.之后合并同类关系,合并 ( a , b ) , ( a + n , b + n ) , ( a + 2 ∗ n , b + 2 ∗ n ) (a,b),(a+n,b+n),(a+2*n,b+2*n) (a,b),(a+n,b+n),(a+2∗n,b+2∗n)即可,因为 a a a与 b b b是同类,也就说明 a a a与 b b b可以同时为天敌 或者 猎物

对于吃关系$(a,b)$的判断:指a吃b

1.首先判断是否冲突,也就是说是否存在 a a a, b b b同类 或者 b b b吃 a a a 的现象

2.之后合并吃关系,合并非常简单自己看代码推一下吧。

Code:

/*** keep hungry and calm CoolGuang!  ***/
/*#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)*/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn];
int Find(int x){
	return  x == pre[x] ? x: pre[x] = Find(pre[x]);
}
int main(){

	read(n);read(m);
	for(int i=1;i<=3*n;i++) pre[i] = i;
	int ans = 0;
	for(int i=1;i<=m;i++){
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(x>n || y > n){
			ans++;
			continue;
		}
		if(op == 2 && x == y){
			ans++;
			continue;
		}
		if(op == 1){///维护同类
			int ax = Find(x),ay = Find(y),bx = Find(x+n),by = Find(y+n),cx = Find(x+2*n),cy = Find(y+2*n);
			if(by == cx || bx == cy) ans++;
			else pre[ax] = ay,pre[bx] = by,pre[cx] = cy;
		}else{
			///x吃y
			int ax = Find(x),ay = Find(y),bx = Find(x+n),by = Find(y+n),cx = Find(x+2*n),cy = Find(y+2*n);
			if(by == cx || ax == ay) ans++;
			else pre[ay] = cx,pre[ax] = by,pre[bx] = cy;
		}
	}
	di(ans);
	return 0;

}

E. 超市

题目大意:

给出一些商品的价值与截止时间,问最多能卖多少钱

题目思路:

贪心的考虑,在没到截至时间的情况下,肯定贪心的去卖价值大的

所以此时要按价值从大到小排序,表示能卖就卖。

如何知道“能卖”呢?

在该商品的截止时间之前,看是否存在一个空闲时间即可,但不可以随便找一个空闲时间,防止 后面有截止时间小的,此时还要找最大的空闲时间。

所以题目转换为了,每次找到一个小于当前时间的最大的时间,如果能找到就说明“能卖” 并 占用,否则不可。

这种问题模型有多种解法,二分维护最小值也可以,这里的并查集是最高效的解法:
初始令所有的 p r e i pre_i prei​都指向 i − 1 i-1 i−1,然后就变成了一个链表,但是由于并查集可以路径压缩,所以可以省去中间已经占用的点。

复杂度 O ( N ) O(N) O(N)

Code:

/*** keep hungry and calm CoolGuang!  ***/
/*#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)*/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn];
int vis[maxn];
int Find(int x){
	if(!vis[x]) return x;
	return pre[x] = Find(pre[x]); 
}
struct node{
	int w,id;
	bool friend operator<(node a,node b){return a.w > b.w;}
}q[maxn];
int main(){
	while(~scanf("%lld",&n)){
		for(int i=1;i<=10000;i++) pre[i] = i-1,vis[i] = 0;
		ll ans = 0;
		for(int i=1;i<=n;i++){
			read(q[i].w);
			read(q[i].id);
		}
		sort(q+1,q+1+n);
		for(int i=1;i<=n;i++){
			int op = Find(q[i].id);
			if(op){
				ans += q[i].w;
				vis[op] = 1;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;

}

F. 奇偶博弈

题目大意:

给出 N N N限制: l i , r i l_i,r_i li​,ri​区间 [ l i , r i ] [l_i,r_i] [li​,ri​]的和为偶数或者奇数

输出最大 x x x,满足 1 − x 1 - x 1−x之间的限制合法

题目思路:

限制合法也就是说,不可以出现冲突

首先将题目给出的进行转换: 令 f ( x ) f(x) f(x)为区间 [ 1 , x ] [1,x] [1,x]的和

那么区间 [ l i , r i ] [l_i,r_i] [li​,ri​]和是偶数 等价于 ( f ( r i ) − f ( l i − 1 ) ) % 2 = = 0 (f(r_i) - f(l_i-1))\%2 == 0 (f(ri​)−f(li​−1))%2==0

也就说 f ( r i ) f(r_i) f(ri​) 与 f ( l i − 1 ) f(l_i-1) f(li​−1)对 2 2 2取余相同,同理是奇数则不同

所以每个点建两个点,奇数点 x x x和偶数点 y + n y+n y+n,对于给出如果和为奇数,那么:就可以连边: ( x , y + n ) ( y , x + n ) (x,y+n)(y,x+n) (x,y+n)(y,x+n),反之同理

如何判断冲突呢?当且仅当 x x x与 x + n x+n x+n在同一个集合内就出现冲突了

当然这个题肯定是可以带权并查集写的,只不过种类并查集好理解而已。(有能力的可以推一下带权并查集)

Code:

/*** keep hungry and calm CoolGuang!  ***/
/*#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)*/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn];
int vis[maxn];
int Find(int x){
	return pre[x] == x?x:pre[x] = Find(pre[x]);
}
struct node{
	int x,y;
	char op[10];
}q[maxn];
vector<int>v;
int getid(int x){
	return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
}
int main(){
	read(n);read(m);

	for(int i=1;i<=m;i++){
		scanf("%d%d%s",&q[i].x,&q[i].y,q[i].op);
		v.push_back(q[i].x-1);
		v.push_back(q[i].y);
	}
	sort(v.begin(),v.end());
	v.erase((unique(v.begin(),v.end())),v.end());
	int sz = v.size();
	for(int i=1;i<=2*sz;i++) pre[i] = i;
	for(int i=1;i<=m;i++){
		int idx = getid(q[i].x-1),idy = getid(q[i].y);
		if(q[i].op[0] == 'e'){
			int dx = Find(idx),dy = Find(idy);
			pre[dx] = dy;
			dx = Find(idx+sz),dy = Find(idy+sz);
			pre[dx] = dy;

		}else{
			int dx = Find(idx),dy = Find(idy+sz);
			pre[dx] = dy;
			dx = Find(idx+sz),dy = Find(idy);
			pre[dx] = dy;
		}
		if(Find(idx) == Find(idx+sz) || Find(idy) == Find(idy+sz)){
			printf("%d\n",i-1);
			return 0;
		}
	}
	printf("%lld\n",m);
	return 0;

}

G.天使与恶魔

题目大意:

有 m m m个天使, p p p个恶魔,天使永远说真话,恶魔永远说假话。
下面给出n条语言:

x , y , y e s x,y,yes x,y,yes 代表 x x x说 y y y是天使 x , y , n o x,y,no x,y,no代表 x x x说 y y y不是天使

问是否存在唯一一种方案使得有 m m m个天使, p p p个恶魔?

如果存在吧啦吧啦,不存在巴啦啦~

题目思路:

带权并查集 + dp路径还原

有能力就做一下,这里讲的不深入,如果想学习可以 Q Q QQ QQ私信我

利用带权并查集推出每个节点与所在联通块根的关系,那么就把每个连通块内分成了两类,同类和异类

然后利用分组背包,将每个连通块看成一个组,同类一样物品,异类一样物品,每组只能选一个,没组必须选,看方案数是否唯一即可

最后根据背包 d p dp dp的性质和上面的要求进行路径还原即可。

Code:

/*** keep hungry and calm CoolGuang!  ***/
/*#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3)*/
//#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17+7;
const ll maxn = 2e6+700;
const ll mod= 1e9+7;
const ll up = 1e13;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int pre[maxn],rk[maxn];///rk_i带权并查集
int vis[maxn];
int Find(int x){
	if(pre[x] == x) return x;
	int t = pre[x];
	pre[x] = Find(pre[x]);
	rk[x] = rk[x]^rk[t];
	return pre[x];
}
int w[maxn][2];
int save[maxn];
int dp[1005][305],visp[maxn];
int main(){
	while(~scanf("%lld%lld%lld",&n,&m,&p)){
		if(n == 0 && m == 0 && p == 0) break;
		for(int i=1;i<=m+p;i++) pre[i] = i,rk[i] = 0;
		for(int i=1;i<=m+p;i++) w[i][0] = w[i][1] = 0,vis[i] = 0;
		
		for(int i=1;i<=n;i++){
			char op[5];int x,y;
			scanf("%d%d%s",&x,&y,op);
			if(op[0] == 'n'){
				int dx = Find(x),dy = Find(y);
				if(dx != dy){
					pre[dx] = dy;
					rk[dx] = !(rk[x] ^ rk[y]);
				}
			}else{
				int dx = Find(x),dy = Find(y);
				if(dx != dy){
					pre[dx] = dy;
					rk[dx] = (rk[x] ^ rk[y]);
				}
			}
		}

		int cnt = 0;
		for(int i=1;i<=m+p;i++){
			int dx = Find(i);
			w[dx][rk[i]]++;
			if(!vis[dx]) vis[dx] = 1,save[++cnt] = dx;
		}

		memset(dp,0,sizeof(dp));
		dp[0][0] = 1;
		for(int i=1;i<=cnt;i++) visp[i] = 0;
		for(int i=1;i<=cnt;i++){
			int dx = save[i];
			for(int k=m;k>=w[dx][0];k--)
				dp[i][k] += dp[i-1][k-w[dx][0]];
			for(int k=m;k>=w[dx][1];k--)
				dp[i][k] += dp[i-1][k-w[dx][1]];
		}
		memset(visp,0,sizeof(visp));
		if(dp[cnt][m] == 1){
			ll y = m;
			for(int i=cnt;i>=1;i--){
				if(y>=w[save[i]][0] && dp[i-1][y-w[save[i]][0]] == 1){
					 visp[save[i]] = 0;
					 y -= w[save[i]][0];
				}else if(y>=w[save[i]][1] && dp[i-1][y-w[save[i]][1]] == 1){
					 visp[save[i]] = 1;
					 y -= w[save[i]][1];
				}
			}
			for(int i=1;i<=m+p;i++){
				int dx = Find(i);
				if(!visp[dx] && !rk[i]) printf("%d\n",i);
				if(visp[dx] && rk[i]) printf("%d\n",i);
			}
			printf("end\n");
		}else puts("no");
	}
	return 0;

}
/***
10
2
1 2 even
1 3 odd
***/

附言

光光能有什么坏心思呢,写这么久希望大家有所提高罢了。

栏目