$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$
笔记：
并查集其实就是个集合，然后就没有然后了。
对于集合呢……我们很容易就可以想到两个操作：合并与查询。
这也就是本题的考察点。
这个问题呢……我们先用暴力思路做一遍：
我们设$s_a$表示元素$a$在$s_a$这个集合内。
那么询问操作其实很好做：也就是等价于判定$s_a=s_b$是否满足。
然而合并操作捏？
我们就需要$O(n)$遍历所有元素进行合并了。这样效率太低了，所以，我们引入——————
$$\Huge并查集$$
并查集的做法呢……
我们用树的形式维护这个集合，根节点的编号就是集合的编号。
所以对于每个点$x$，记$fa_x$为$x$的父节点。
再引入一个函数$find(x)$，表示$x$所属的集合。
除了根节点外，其它点都不满足$fa(x)==x$，也就是说根节点的父节点是自己（自己属于自己这个集合）。
那么相同的，在初始化$init()$的时候，我们就要把每个节点的父节点$fa_i$设定为$i$，自己为一个集合。
而$find(x)$函数如何设计呢？
whlie (fa[x] != x) x = a[x]; 最后$x$即为集合编号。
对于询问操作，查询两个节点的所在集合$find$是否相同即可。
合并两个集合的操作$merge(a,b)$又如何实现？
首先求出$a$和$b$的集合编号$x$和$y$。
$x$、$y$是根节点，那么就可以进行合并了。
我们把$y$的父节点设为$x$，就把$y$合并到了$x$。
至此，基础部分就介绍完了。
还有进阶呢！
如果并查集退化成了链，那么每次操作都是$O(n)$的了……
加大数据范围之后，就会$TLE$。
我们考虑进行优化。
$Step_1$路径压缩优化——$O(n log n)$
原算法既然在$find$上浪费了时间，我们就考虑优化$find$。
我们知道并查集是因为链状数据而超时，那么我们就针对这种数据思考：
可以将这个点到根节点路径上的所有节点，全部指向根节点。
这样可能说得有点直接。。。我们慢慢理解。
既然这棵树上这个节点（设为$x$）到根节点的路径上那些点（设其中一个为$y$）在进行$find$的时候都要重新往根节点走一遍，那还不如直接把$x$指向根节点，顺便把$y$也一起连带着往根节点指过去，这样就优化很多了，路径上的那些节点在$find$的时候就只需要$O(1)$的时间复杂度，直接到了根节点。
参考代码：
int find(int x) {
if (fa[x] != x) fa[x] = find(fa[x]);
else return fa[x];
}
$Step_2$按秩合并优化——$O(n log n)$
虽然$Step_1$路径压缩优化已经可以很高效地解决$TLE$的问题，但是如果树的形态有意义的话，一但进行路径压缩，就会导致形态发生变化，从而影响答案。
因此我们可以转而沿着不破坏树的方向考虑优化。
如果说我们把小的集合合并到大的集合上面会怎么样呢？
没错，这就是按秩合并的思路。
我们在初始化$init()$的时候增加一个$size_x=1$，也就是$x$集合初始大小为1。
在每次合并的时候，把小的$size$加到大的$size$上面。
这样的时间复杂度也是$O(n log n)$的。
$Step_3$一起上！——$O(......)$
不要问我为什么时间复杂度是这样。。。
因为我也不知道它具体是啥，只是知道它叫反阿克曼函数，增长很缓慢，接近于一个常数，且非常小。
$Step_4$结束啦！发代码咯
不过我懒只写了路径压缩优化的代码……
#include<bits/stdc++.h>
using namespace std;
int n, m;
int fa[100010];
int get(int x){
if(x == fa[x]) return x;
return fa[x] = get(fa[x]);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
char ch; cin>>ch; int a, b;cin>>a>>b;
if(ch == 'M'){
if(get(a) != get(b)) fa[get(a)] = get(b);
}
else{
if(get(a) != get(b))puts("No");
else puts("Yes");
}
}
return 0;
}
路径压缩和按秩序合并的时间复杂度都是 $O(\log n)$，两者加起来是 $O(\alpha(N))$，对于 $\forall \ N \leq 2^{2^{10^{19729}}}$，都有 $\alpha(N) < 5$。
啊对对对
orzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorz
orzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorzorz