【合并集合】

基本 *** 作: 模板题

并查集:最优美的数据结构

建议多敲几遍理解 本题模板的路径压缩, 有兴趣的可以了解一下按秩合并的优化方式, 当路径优化和按秩合并在一起时, 他们的时间复杂度将是 O(n(α)) 的大小

#include 
#define int long long

using namespace std;

const int N = 1e5 + 10;

int fa[N];
int n, m;

int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]); // 非常简洁的写法
}
signed main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++ )
        fa[i] = i; // 注意要初始化
    
    while(m -- )
    {
        char op;
        int s1, s2;
        cin >> op >> s1 >> s2;
        
        
        if(op == 'M') fa[find(s1)] = find(s2);
        else 
        {
            if(find(s1) != find(s2)) cout << "No" << endl;
            else cout << "Yes" << endl;
        }
    }
}