C++ 代码

// 并查集，本来查询时间复杂度为O（n），现在变为O（1）会比较好
#include <iostream>
using namespace std;
const int N = 1e5+10;
int p[N];

// find最多走两步，而且走完之后直接复制，把顶点值给了这个节点
int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    // 初始化
    for(int i = 1; i <= n; i++)
        p[i] = i;

    int a, b;
    char command;
    while(m--)
    {
        cin >> command >> a >> b;
        if(command == 'M')
            p[find(a)] = find(b);
        else
            (find(a) == find(b))? cout << "Yes" << endl : cout << "No" << endl;
    }
    return 0;
}