简单并查集算法模板

并查集

简单并查集
基本思想：
采用双亲表示法，顺序存储。
课本做法：
①初始化数组的值为-1
②若是合并就让一个树的根的数组值指向另一个根的下标
③（查根节点）若是查询就一直到数组值小于0的时候终止
时间复杂度为O(n)

优化：查的过程，并且观察到时间复杂度和树的高度有关即：
①小树合并到大树
②判断小树和大树，将数组根节点的值的绝对值作为大小判断。
时间复杂度为O(log2n)

Y总模板做法（未优化）：
①全部初始化为自己的下标值
②若是合并也是将一个集合的根节点的数组值指向另一个集合的根节点的下标
③（查根节点）若是查就查他数组中的值是不是自己的下标即可（下标从1开始） 

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1e5 +10;
int st[N];
int n,m;

int find(int x)
{
    if(st[x]!=x)
    st[x]=find(st[x]);
    else
    return st[x];
}

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        st[i]=i;
        
    while(m--)
    {
        char op;
        cin >> op;
        int a,b;
        cin >> a >> b;
        if(op=='M')
        {   
            //采用的是树的双亲表示法存储的
            //数组中存储的是双亲的下标
            st[find(a)]=find(b);
        }
        else if(op=='Q')
        {
            if(find(a)==find(b))
            cout << "Yes" << endl;
            else
            cout << "No" << endl;
        }
    }
    return 0;
}