本蒟蒻的第8篇题解

题目传送门

读了题目可以发现，这就是个并查集的 模板题，基本是不需要夺取讲，这里就讲下算法的基础思路

1.是什么

简单的理解成认爹，例如把a和b放到一个集合中，就是把a当b的爹，再往后加入，就把这个《族谱》往后写，这样就算是放到一个集合里了。之后再要调用这类的数或者查找是否在一个集合，就可以直接调用这个《族谱》。

2.怎么做

并查集基础的东西就三个

1. find函数（找最老的祖宗（爹的爹的爹....））。
2. merge函数（查找是否在一个集合内）。
3. init函数（初始化）

3.怎么写

find函数（路径压缩版）

前面也说了，find函数就是去找祖宗，祖宗又是爹的爹的爹...，所以说，可以用一个s[i]数组表示第i个数祖宗。同样是开头的a和b，即s[b]=a(我没有骂人，真的没有👀️ )

代码：

int find(int x){
	if(x!=s[x]) s[x]=find(s[x]);//如果自己有爹，就往上接着找。自己调用自己。
	return s[x];
}

merge函数

查找怎么在一个集合内，这是可能会有聪明的同学问 Q:"万一a的儿子是c而b的爹是c，那么a!=s[b]，该怎么判断。” A:"1.我们用的是路径压缩，即只有一个爹，不同担心这方面的问题2.即使没有用，我们的find数组本质上是找最老的祖宗，所以只要在一个集合内，就不同怕！"

找祖宗，用find函数 即如果a的祖宗和b的祖宗是同一个数，他们就在一个集合内

代码：

void merge(int x,int y){
x=find(x);//找到x的祖宗
y=find(y);//找到y的祖宗
if(x!=y) s[x]=y;//判断在不在一个集合内
}

init函数

初始化初始什么？明显的，是s数组。将每个数的爹设为自己即可，这样相当于它没有加入任何的集合（虽然感觉自己是自己爹好奇怪）。

代码：

void init(){
	for(int i=1;i<=n;i++) s[i]=i;
}

4.主函数内容

不多bb，直接上代码

int a,b;
	cin>>n>>m;
	init();
	while(m--){
		cin>>q>>a>>b;
		if(q=='M') {
			merge(a,b);
		}
		if(q=='Q') {
			if(find(a)==find(b)) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
		}
	}
		
			
	return 0;

这里的坑点在于，不要把init初始化放在最前面，不然的话连n都没输入，会啥用也没有哦！

5.完整的代码

#include<iostream>
using namespace std;
const int N=10010;
int s[N];
int n,m;
char q;
int find(int x){
	if(x!=s[x]) s[x]=find(s[x]);
	return s[x];
}
void merge(int x,int y){
	x=find(x);
	y=find(y);
	if(x!=y) s[x]=y;
}

void init(){
	for(int i=1;i<=n;i++) s[i]=i;
}
int main(){
	int a,b;
	cin>>n>>m;
	init();
	while(m--){
		cin>>q>>a>>b;
		if(q=='M') {
			merge(a,b);
		}
		if(q=='Q') {
			if(find(a)==find(b)) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
		}
	}
		
			
	return 0;
}

偷偷告诉你们，我就是把init放到了开头，调了10分钟才发现😄 。 最后，本题解如有错误，欢迎直接指出！