【题解】校运会
【题目描述】
校运会上，一共有N个参赛选手，已知N个选手的名字。然后老师告诉你M句话，话的内容是学生A与学生B在同一组里。如果学生A与学生B在同一组里，学生B与学生C也在同一组里，就说明学生A与学生C在同一组。
然后老师问你K句话，即学生X和学生Y是否在同一组里。若是，输出Yes，否则输出No。
【输入描述】
第一行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;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。