【题目描述】

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

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

$2\le �\le 2\times 10^{\mathrm{4<span\; class="s9f4f40">参赛选手。（尼玛全校学生都没这么多吧）</span>}}$

【输入描述】

第一行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;	  }

(adsbygoogle = window.adsbygoogle || []).push({});