并查集

并查集

1.将两个集合合并
2.询问两个元素是否在一个集合当中

#include <iostream>
using namespace std;
 
const int N = 100010;

int n, m;
int p[N];

//返回x的根节点 + 路径压缩
int find(int x){
	//p[x] != x
	//因为每个集合只有根节点的值等于自己
	//p[x] = find(p[x])
	//直到找到它的根节点，之后会返回根节点的值
	//同时在此过程中，每个节点父节点的值都会变成根节点的值
	//由此完成路径压缩
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) p[i] = i;
	
	while(m--){
		string op;
		cin >> op;
		int a, b;
		cin >> a >> b;
		if (op == "M") {
			//将b所在集合的根节点视为a所在集合的根节点的父节点
			p[find(a)] = find(b);
		} else {
			if (find(a) == find(b)) cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}
	
	return 0;
}