首页 > 其他分享 >并查集（水题）

并查集（水题）

时间：2024-04-08 13:05:19浏览次数：31  
标签：return 水题 fa int fy 查集 fx find

A. 是不是亲戚

题目描述

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

规定：x 和 y 是亲戚，y 和 z 是亲戚，那么 x 和 z 也是亲戚。如果 x,y 是亲戚，那么 x 的亲戚都是 y 的亲戚，y 的亲戚也都是 x 的亲戚。

输入：

第一行：三个整数 n,m,p，（n≤5000,m≤5000,p≤5000 ），分别表示有 n 个人，m 个亲戚关系，询问 p 对亲戚关系。

以下 m 行：每行两个数 Mi​,Mj​，1≤Mi​,Mj​≤N，表示 Mi​ 和 Mj​ 具有亲戚关系。

接下来 p 行：每行两个数 Pi​,Pj​，询问 Pi​ 和 Pj​ 是否具有亲戚关系。

输出：

P行，每行一个 Yes 或 No。表示第 i 个询问的答案为“具有”或“不具有”亲戚关系。

样例：

输入

6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

输出

Yes
Yes
No

代码如下：

#include<bits/stdc++.h>
using namespace std;
int fa[5010];
int n,m,q;
int find(int x){
	if(fa[x]==x) return x;
	else return find(fa[x]);
}
void merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy){
		fa[fx]=fy;
	}
}
int main(){
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	int x,y;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		merge(x,y);
	}
	for(int i=1;i<=q;i++){
		cin>>x>>y;
		if(find(x)==find(y)){
			cout<<"Yes"<<endl;
		}else{
			cout<<"No"<<endl;
		}
	}
	return 0;
}

B. 修路

题目描述：

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。

请你计算出最少还需要建设多少条道路？

输入：

输入包含若干组测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目 n 和道路数目 m （输入 n=0 表示测试数据结束）；

随后的 m 行对应 m 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 1 到 n 编号。

注意：两个城市间可以有多条道路相通。

对于 100% 的数据，保证 1≤n<1000 。

输出：

对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。

样例：

输入：

4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

输出

1
0
2
998

代码如下：

#include<bits/stdc++.h>
using namespace std;
int fa[1010];
int n,m;
int find(int x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy){
		fa[fx]=fy;
	}
}
int main(){
	while(1){
		cin>>n;
		if(n==0) break;
		cin>>m;
		for(int i=1;i<=n;i++) fa[i]=i;
		int x,y;
		for(int i=1;i<=m;i++){
			cin>>x>>y;
			merge(x,y);
		}
		int c=0;
		for(int i=1;i<=n;i++){
			if(fa[i]==i) c++;
		}
		cout<<c-1<<endl;
	}
	return 0;
}

C. 躲避拥堵的最佳路线

题目描述：

小明所在的城镇有 m 条路连接了 n 个区（ n 个区的编号在 1∼n 的范围内），每条大道将两个区相连接，每条大道有一个拥挤度。

小明想要开车从 s 区去 t 区，请你帮他规划一条路线，使得经过道路的拥挤度的最大值最小。

输入：

第一行有四个用空格隔开的 n,m,s,t ，其含义见题目描述。

接下来 m 行，每行三个整数 u,v,w ，表示有一条大道连接区 u 和区 v，且拥挤度为 w ，道路为双向道路，两个方向都可以走。

两个区之间可能存在多条大道。

数据规模与约定：

对于 30% 的数据，保证 n≤10 。

对于 60% 的数据，保证 n≤100 。

对于 100% 的数据，保证 1≤n≤10^4，1≤m≤2×10^4,，w≤10^4，1≤s,t≤n。

且从 s 出发一定能到达 t 区。

输出：

输出一行一个整数，代表最大的拥挤度。

样例：

输入：

3 3 1 3
1 2 2
2 3 1
1 3 3

输出：

2

代码如下：

#include<bits/stdc++.h>
using namespace std;
int fa[10010];
int n,m,s,t,l=INT_MAX,r=INT_MIN,mid;
struct city{
	int x,y,len; 
}a[20010]; 
int find(int x){
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy){
		fa[fx]=fy;
	}
}
bool check(int mid){
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		 if(a[i].len<=mid){
		 	merge(a[i].x,a[i].y);
		 }
	}
	return find(s)==find(t);
}
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y>>a[i].len;
		l=min(l,a[i].len);
		r=max(r,a[i].len);
	} 
	while(l<=r){
		mid= l + r >> 1;
		if(check(mid)) r=mid-1;
		else l=mid+1;
	}
	cout<<l;
	return 0;
}

D. 团队数量

题目描述：

芝加哥组织了一场激烈的军事竞赛，很多国家的军人慕名而来，他们要么是队友，要么是敌人。

现建立如下规则：

  1. 我的队友的队友，是我的队友；

  2. 我的敌人的敌人也是我的队友；

两个人只要是队友，就认为他们属于同一团队，现给你若干参赛军人之间的关系，请问：最多有多少个团队？

输入：

第一行是一个整数 N (2≤N≤1000)，表示参赛的人数（从 1 编号到 N ）。

第二行 M (1≤M≤5000)，表示关于参赛者的关系信息的条数。

以下 M 行，每行可能是 F p q 或是 E p q（1≤p,q≤N），F 表示 p 和 q 是队友，E 表示 p 和 q 是敌人。

输入数据保证不会产生信息的矛盾。

输出：

输出文件只有一行，表示最大可能的团队数。

样例：

输入：

6
4
E 1 4
F 3 5
F 4 6
E 1 2

输出：

3

代码如下：

#include<bits/stdc++.h>
using namespace std;
int f[5010];
int n,m;
int find(int x){
	return x == f[x]?x:f[x]=find(f[x]);
}
void merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy){
		f[fx]=fy;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=2*n;i++){
		f[i]=i;
	}
	char c;
	int x,y;
	for(int i=1;i<=m;i++){
		cin>>c>>x>>y;
		if(c=='F') merge(x,y);
		else{
			merge(y+n,x);
			merge(x+n,y);
		}
	}
	int r=0;
	for(int i=1;i<=n;i++){
		if(f[i]==i) r++;
	}
	cout<<r;
	return 0;
}

E. 关押罪犯（这题是NOIP原题，有亿点难，新手勿做！）

题目描述：

S 城现有两座监狱，一共关押着 N 名罪犯，编号分别为 1−N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。

每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。

在详细考察了 N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。

那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？

输入：

每行中两个数之间用一个空格隔开。

第一行为两个正整数 N,M，分别表示罪犯的数目以及存在仇恨的罪犯对数。

接下来的 M 行每行为三个正整数 aj,bj​,cj​，表示 aj​ 号和 bj​ 号罪犯之间存在仇恨，其怨气值为 cj​。

数据保证 1<aj​≤bj​≤N，0<cj​≤10^9，且每对罪犯组合只出现一次。

输出：

共 1 行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 0。

样例：

输入：

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

输出：

3512

代码如下：

#include<bits/stdc++.h>
using namespace std;
int f[40010];
int n,m;
struct node{
	int x,y,v;
}a[100010]; 
int find(int x){
	return x == f[x]?x:f[x]=find(f[x]);
}
bool cmp(node n1,node n2){
	return n1.v>n2.v;
}
void merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy){
		f[fx]=fy;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y>>a[i].v;
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=n*2;i++){
		f[i]=i; 
	}
	for(int i=1;i<=m;i++){
		if(find(a[i].x)==find(a[i].y)){
			cout<<a[i].v;
			return 0;
		}else{
			merge(a[i].x+n,a[i].y);
			merge(a[i].y+n,a[i].x);
		}
	}
	cout<<0;
	return 0;
}

F. 最短网络 Agri-Net（USACO3.1）（更难！！！）

题目描述：

Farmer John 被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。

FJ 已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过 10^5 。

输入：

第一行农场的个数 N（3≤N≤100）。

接下来是一个 N × N 的矩阵，表示每个农场之间的距离。理论上，他们是 N 行，每行由 N 个用空格分隔的数组成，实际上，由于每行 80 个字符的限制，因此，某些行会紧接着另一些行。当然，对角线将会是 0 ，因为不会有线路从第 i 个农场到它本身。

输出：

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

样例：

输入：

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

输出：

28

代码如下：

#include<bits/stdc++.h>
using namespace std;
int f[110];
int n,t,k;
struct node{
	int x,y,len;
}a[6000]; 
int find(int x){
	return x == f[x]?x:f[x]=find(f[x]);
}
bool cmp(node n1,node n2){
	return n1.len<n2.len;
}
void merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy){
		f[fx]=fy;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>t;
			if(i<j){
				k++;
				a[k].x=i;
				a[k].y=j;
				a[k].len=t;
			}
		}
	}
	sort(a+1,a+k+1,cmp);
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	int s=0,c=0;
	for(int i=1;i<=k;i++){
		int fx=find(a[i].x);
		int fy=find(a[i].y);
		if(fx!=fy){
			f[fx]=fy;
			c++;
			s=s+a[i].len;
		}
		if(c==n-1){
			cout<<s;
			break;
		}
	}
	return 0;
}

G. 立方体积木Cube Stacking（也挺难）

题目描述：

约翰和贝茜在玩一个方块游戏。编号为 1……n 的 n ( 1≤n≤30000 ) 个方块正放在地上，每个构成一个立方柱。
游戏开始后，约翰会给贝茜发出 P ( 1≤P≤100000 ) 个指令。指令有两种：
移动（M）：将包含 X 的立方柱移动到包含 Y 的立方柱上。
统计（C）：统计含 X 的立方柱中，在 X 下方的方块数目。
写个程序帮贝茜完成游戏。

输入：

第 1 行输入 P，之后 P 行每行输入一条指令，形式为 M X Y 或者 C X。
输入保证不会有将立方柱放在自己头上的指令。

输出：

输出共 P 行，对于每个统计指令，输出其结果。

样例：

输入：

6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4

输出：

1
0
2

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=30010;
int f[N];
int dis[N];
int len[N];
int p;
int find(int x){
	if(f[x]==x) return x;
	else{
		int t=f[x];
		f[x]=find(f[x]);
		dis[x]=dis[x]+dis[t];
		return f[x];
	} 
}
void merge(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy){
		f[fx]=fy;
		dis[fx]=dis[fx]+len[fy];
		len[fy]=len[fy]+len[fx];
		len[fx]=0;
	}
}
int main(){
	cin>>p;
	for(int i=1;i<=30000;i++){
		f[i]=i;
		len[i]=1;
	}
	char c;
	int x,y;
	for(int i=1;i<=p;i++){
		cin>>c>>x;
		if(c=='C'){
			find(x);
			cout<<dis[x]<<endl;
		}else{
			cin>>y;
			merge(x,y);
		}
	} 
	return 0;
}

温馨提示：

这些"水题"的题目是作者复制的，代码是作者自己做的，看官们请自己做一遍，锻炼锻炼自己的写代码能力，还有！不了解并查集的请看——并查集概述呦！！！

本作者希望看官们能多多评论，谢谢啦！！！

制作不易，点个赞吧！！！

制作不易，点个赞吧！！！

制作不易，点个赞吧！！！

标签：return,水题,fa,int,fy,查集,fx,find
From： https://blog.csdn.net/Ryan_hsMax/article/details/137503272

相关文章

  • 并查集概述
    目录并查集概述并查集一般要处理的问题并查集的实现方法最后（求看）并查集概述并查集是一种树型的数据结构，由于处理一些不相交集合的合并及查询问题。并查集思想是用一个数组表示了整片森林，树的根节点唯一是一个集合的标识，我们只要找到了某个元素的树确定它在哪个集合里。......
  • 高级数据结构-并查集plus（更新中。。。
    格子游戏题目链接：格子游戏思路：首先围成一个闭环的时候，两个点一定有边相连，那么可以把这两个点通过并查集连在一个连通块里面，如果两个点的父亲相同，那么就形成闭环。同时，为了方便可以将二维的图转化成一维的进行计算，k=x*n+y，x,y要从0开始统计。代码附上：#include<bits/stdc++.h......
  • 并查集——蓝桥杯备赛【python】
    一、合根植物试题链接：[蓝桥杯2017国C]合根植物问题描述星球的一个种植园，被分成m×n个小格子(东西方向m行，南北方向n列)。每个格子里种了一株合根植物。这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。如果我们告诉你哪些小......
  • 并查集解题思路
    概述并查集主要是解决以下几种问题的：各节点之间的关系某节点和它祖先之间的关系种类朴素并查集，一个集合的信息可以存储在它的祖先节点上。带权并查集，维护的是某节点与它祖先的关系。扩展域并查集（种类并查集），本质是多开几倍空间的朴素并查集，维护的是各个阵营之间的关系，且......
  • 并查集学习笔记
    并查集学习笔记本质上还是一个复习笔记。考虑这样一个问题：给出\(x,y\)，合并\(x,y\)所在集合。给出\(x,y\)，查询\(x,y\)是否在同一集合内。我们把集合当成一棵树，两个点有连边就表示他们在同一个集合内。这棵树的根节点就是这个集合的“老大”，也就是这个集合里面的......
  • 并查集
    并查集的作用检查图中是否存在环并查集的流程设定一个集合，叫并查集往集合里面添加边，怎么添加呢？取边的起点和终点，判断两点是否都在集合里面。如果都在，则出现了环，如果不在，则将两个点放入集合中。继续添加下一条边，直到没有边。如果最后都没有找到环，就是图中不存在环。并......
  • 代码随想录 | 图论 797. 所有可能的路径（dfs） ，200. 岛屿数量 （dfs）200. 岛屿数量 （bfs）
    797.所有可能的路径https://leetcode.cn/problems/all-paths-from-source-to-target/description/List<List<Integer>>res;List<Integer>path;publicList<List<Integer>>allPathsSourceTarget(int[][]graph){res=newA......
  • 【算法】BFS、并查集和拓扑排序
    最近刷到了两道关于图论很有意思的题目（）。做法颇有相似之处，因此记录一下吧AcWing2069.网络分析标签:dfs、并查集题目描述题目大意是，有一个\(n\)个顶点的网络，初始状态图中没有边。有两种操作：操作1将节点\(a\)和节点\(b\)连接起来；操作2使节点\(p\)的值加\(t\)，\(t\)值会沿着网......
  • Luogu P8710 [蓝桥杯 2020 省 AB1] 网络分析 题解 [ 绿 ] [ 带权并查集 ]
    原题分析本题由于从一个节点发信息，同一个集合内的所有点都会收到信息，显然是一道要求维护各节点间关系的题，因此采用并查集的数据结构进行求解。但由于维护关系的同时还要维护权值，所以采用带权并查集，它是一种能维护某个节点与其祖宗节点之间关系的数据结构。带权并查集找父亲的......
  • 并查集(小白)
    许久未更新今天小小的学习一下 让我开始我们的学习之旅 并查集引入首先我们引入一个概念,并查集是管理元素所属集合的数据结构,可以理解为一个集合一棵树---这一颗树的每个节点都是一个元素。比如图中的元素1,2,3,4,5属于一个集合,元素6,7,8属于一个集合并查......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99