2022.1.18

目录

P3367 【模板】并查集

题目描述

输入格式

输出格式

输入输出样例

说明/提示

思路

代码实现

P1551 亲戚

题目背景

题目描述

输入格式

输出格式

输入输出样例

思路

代码实现 


学习了二叉树和并查集,并进行了整理后,做了几个题练手

P3367 【模板】并查集

题目描述

如题,现在有一个并查集,你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,MN,M ,表示共有 NN 个元素和 MM 个操作。

接下来 MM 行,每行包含三个整数 Z_i,X_i,Y_iZi​,Xi​,Yi​ 。

当 Z_i=1Zi​=1 时,将 X_iXi​ 与 Y_iYi​ 所在的集合合并。

当 Z_i=2Zi​=2 时,输出 X_iXi​ 与 Y_iYi​ 是否在同一集合内,是的输出 Y ;否则输出 N 。

输出格式

对于每一个 Z_i=2Zi​=2 的操作,都有一行输出,每行包含一个大写字母,为 Y 或者 N 。

输入输出样例

输入 #1复制

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出 #1复制

N
Y
N
Y

说明/提示

对于 30\%30% 的数据,N \le 10N≤10,M \le 20M≤20。

对于 70\%70% 的数据,N \le 100N≤100,M \le 10^3M≤103。

对于 100\%100% 的数据,1\le N \le 10^41≤N≤104,1\le M \le 2\times 10^51≤M≤2×105,1 \le X_i, Y_i \le N1≤Xi​,Yi​≤N,Z_i \in \{ 1, 2 \}Zi​∈{1,2}。

思路

1、初始化祖先为自己

2、假如z==1,进行合并操作(合并操作就是把一个节点的祖先变为另一个节点的祖先。)

3、假如z==2,进行查找x,y的祖先,如果相等输出Y,反之输出N(查找操作就是不断地向上走,直到找到祖先为止)

4、注意压缩路径

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,m,fa[10010];
int z,x,y;
int find(int i)
{
	if(fa[i]==i)
		return i;//递归出口
	else
	{
		fa[i]=find(fa[i]);//路径压缩 
		return fa[i]; 
	}	
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
        fa[i]=i;
	while(m--)
	{
		cin>>z>>x>>y;
		if(z==1)
			fa[find(x)]=find(y);
		else
		{
			if(find(x)==find(y))
				printf("Y\n");
			else
				printf("N\n");
		}
	}
}

P1551 亲戚

题目背景

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

题目描述

规定:xx 和 yy 是亲戚,yy 和 zz 是亲戚,那么 xx 和 zz 也是亲戚。如果 xx,yy 是亲戚,那么 xx 的亲戚都是 yy 的亲戚,yy 的亲戚也都是 xx 的亲戚。

输入格式

第一行:三个整数 n,m,pn,m,p,(n,m,p \le 5000n,m,p≤5000),分别表示有 nn 个人,mm 个亲戚关系,询问 pp 对亲戚关系。

以下 mm 行:每行两个数 M_iMi​,M_jMj​,1 \le M_i,~M_j\le N1≤Mi​, Mj​≤N,表示 M_iMi​ 和 M_jMj​ 具有亲戚关系。

接下来 pp 行:每行两个数 P_i,P_jPi​,Pj​,询问 P_iPi​ 和 P_jPj​ 是否具有亲戚关系。

输出格式

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

输入输出样例

输入 #1复制

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

输出 #1复制

Yes
Yes
No

思路

1、前m组数进行合并操作

2、后p组数进行查找操作

代码实现 

#include<bits/stdc++.h>
using namespace std;
int n,m,p,fa[10010];
int z,x,y;
int find(int i)
{
	if(fa[i]==i)
		return i;//递归出口
	else
	{
		fa[i]=find(fa[i]);//路径压缩 
		return fa[i]; 
	}	
}
int main()
{
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++)
        fa[i]=i;
	while(m--)
	{
		cin>>x>>y;
		fa[find(x)]=find(y);
	}
	while(p--)
	{
		cin>>x>>y;
		if(find(x)==find(y))
				printf("Yes\n");
			else
				printf("No\n");
	}	
	return 0;
}

上一篇:【报告分享】2021中国汽车营销年鉴- 搜狐汽车(附下载)


下一篇:1月18日毒鸡汤:聖人不病,以其病病,夫唯病病,是以不病