AcWing 836. 合并集合

题面：
一共有 \(n\) 个数，编号是 \(1∼n\)，最开始每个数各自在一个集合中。
现在要进行 \(m\) 个操作，操作共有两种：
1、M a b，将编号为 \(a\) 和 \(b\) 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略操作；
2、Q a b，询问编号为 \(a\) 和 \(b\) 的两个数是否在同一个集合中；

原题链接：836. 合并集合 - AcWing

并查集

对lareges大佬的笔记的再总结，自用学习，感谢大佬
原文非常清晰明了，膜拜：下班前几分钟，我彻底弄懂了并查集

• 并查集(Union Find)，也叫「不相交集合(Disjoint Set)」，
  顾名思义，它专门用于动态处理不相交集合的「合并」与「查询」问题。
• 并查集的两种操作：
  • 合并：合并两个元素所属集合；
  • 查询：查询某个元素所属集合。这可以用于判断两个元素是否属于同一集合。
• parent 数组：
  • p[i] 表示编号为 i 的节点的父节点的编号。
  • 特别地，定义根节点的父节点是其自身。
  • 代表元法：把每个集合看成一棵树，节点元素一一对应，根节点称为该集合的代表元。
    • 树的根节点的编号为整个树（集合）的编号，
      对于任一元素 \(x\)，可以自底向上追溯到根节点，来判断它属于哪个集合。
    • 设计理念：三个不重要
      • 谁作为根节点不重要：根节点与非根节点只是位置不同，并没有附加的含义；
      • 树怎么形成的不重要：合并的时候任何一个集合的根节点指向另一个集合的根节点就可以；
      • 树的形态不重要：理由同「谁作为根节点不重要」。
  • p[] 数组的初始化：
    • 根据代表元法，最初每个元素都是一棵树；
    • 树中只有根节点，因此对于任一元素 \(i\) ，都有 \(p [ i ] = i\) 成立。
    • 代码：for (int i = 1; i <= n; i++) p[i] = i;
• 查询：追溯根节点，来判断节点属于哪个集合。
  • 时间复杂度 \(O(n)\)：while (p[x] != x) x = p[x];（\(n\) 为树的高度）
  • 优化方案：路径压缩
    • 从元素 \(x\) 不断追溯到根节点会形成一条路径；
    • 查询结束后，我们将该路径上除了根节点的每个节点都直接连接到根节点上；
    • 在后续的查询过程中，若查询的是该路径上的点，时间复杂度即为 \(O(1)\) 。
• 合并：将其中一棵树的根节点指向另一棵树的根节点，从而合并两棵树。
  • 代码：p[find(a)] = find(b);

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, a, b;
int p[N];	//p[x]: 指向x的父节点
char op;

//返回元素x所属集合的编号
int find(int x) {
	if (p[x] != x) //如果元素x不是根节点
		p[x] = find(p[x]); //让元素x直接指向根节点
	return p[x];  //返回x的父节点的编号
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)  p[i] = i;
	//法二：iota(p, p + n + 1, 0);	//顺序赋值函数iota(起点，终点，起始值)
	while (m--) {
		cin >> op >> a >> b;
		if (op == 'M')
			p[find(a)] = find(b);
		else
			cout << (find(a) == find(b) ? "Yes\n" : "No\n");
	}
}