当前位置:首页 > 题解目录 > 正文内容

【题解】校运会

亿万年的星光2年前 (2023-04-13)题解目录1261

【题目描述】

校运会上,一共有N个参赛选手,已知N个选手的名字。然后老师告诉你M句话,话的内容是学生A与学生B在同一组里。如果学生A与学生B在同一组里,学生B与学生C也在同一组里,就说明学生A与学生C在同一组。

然后老师问你K句话,即学生X和学生Y是否在同一组里。若是,输出Yes,否则输出No。

22×104参赛选手。(尼玛全校学生都没这么多吧)

【输入描述】

第一行N和M。

接下来N行输入每一个同学的名字。

再往下M行每行输入两个名字,且保证这两个名字都在上面 N行中出现过,表示这两个参赛选手在同一个组里。

接下来输入K。

最后输入K个老师的询问。

【输出描述】

对于每一个循环,输出Yes或者No

【样例输入】

10 6
Jack
Mike
ASDA
Michel
brabrabra
HeHe
HeHE
papapa
HeY
Obama
Jack Obama
HeHe HeHE
brabrabra HeHe
Obama ASDA
papapa Obama
Obama HeHE
3
Mike Obama
HeHE Jack
papapa brabrabra

【样例输出】

No.
Yes.
Yes.

【数据范围】

2<=N<=2*10^4
1<=M<=10^6
1<=K<=10^6

【题目分析】

  • 并查集题目,问题就是如何表示字符串这个问题。


我们可以定义一个结构体,参考如下:

struct node{	
	string s; //姓名 
	int num;	//编号 
};

用s表示姓名,用num表示编号,然后左侧的圆圈表示当前这个人的下标。

那么,在以前中并查集中,我们的指向关系中,我们是p[4]=9,那么在结构体中,就是 p[x].num=p[y].num

通过上面这种指向关系确定父级和子级




【参考答案:结构体】

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
struct node{	
	string s;     //姓名 
	int num;	//编号 
};
node p[20005]; 


//查找函数 
int find(int n){	 
	if(p[n].num==n) 
		return p[n].num;
	else  
		return 	p[n].num=find(p[n].num);

}
void merge(int a,int b){	//合并并查集 
	int fa=find(a);
	int fb=find(b);		
	if(fa==fb) return ;
	else p[fa].num=p[fb].num;
	return;
}
//查找这个名字 
int sfind(string a){
	for(int i=1;i<=n;i++){
		if(a==p[i].s) return i;
	}
}
int main(){
	cin>>n>>m;]
	//输入以及初始化 
	for(int i=1;i<=n;i++){
		cin>>p[i].s;	 
		p[i].num=i;
	}	
	//查找并合并 
	for(int i=1;i<=m;i++){
		string x,y;	
		cin>>x>>y;
		if(find(sfind(x))!=find(sfind(y))){	//查找两个名字
			merge(sfind(x),sfind(y));		//合并 
		}
	} 
	cin>>k;	 
	//k次询问 
	for(int i=1;i<=k;i++){	
		string x1,y1;
		cin>>x1>>y1;
		//查找两个名字
		if(find(sfind(x1))==find(sfind(y1))){	
			cout<<"Yes."<<endl;			
		}else {
			cout<<"No."<<endl;		 
		}
	}
	return 0;	
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】装满杯子需要的最短总时长

【题目描述】现有一台饮水机,可以制备冷水、温水和热水。每秒钟,可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。给你一个下标从&nb...

【题解】分发饼干

【题目描述】假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;...

【题解】车辆管理

【题目描述】交通管理局长氓氓现在需要一个管理汽车的系统,每一辆汽车都有许多信息需要去记录。 首先,每一辆汽车都有一个独一无二的车牌号 S,车牌号由 7 个字符组成。 然后,对于每一辆车要记录它的排...

【题解】最大子矩阵

【题目描述】已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 × 1)子矩阵。比如,如下4 × 4的矩阵0  -2 -7&nb...

【题解—动态规划】背包问题1

【题目描述】一个旅行者有一个最多能装 m 公斤物品的背包,现在有 n 件物品,它们的重量分别是 w1,w2,…,wn, 它们的价值分别为 c1,c2,…cn 。若每种物品只有一件,求旅行者能获得的最大...

八皇后问题

八皇后问题

【题目描述】八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行...