时间复杂度

查找由O（n）变成了O（1）

C++ 代码

#include <iostream>
using namespace std;
const int N = 1e5;
int p[N], s[N];

// 并查集的核心就是这个，在O（1）时间内通过一个元素找到它的父节点，最多循环两次
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,s[i] = 1;
    string command;
    int a, b;
    while(m--)
    {
        cin >> command;
        if(command == "C")
        {
            cin >> a >> b;
            if(find(a) == find(b)) continue;
            else s[find(b)] += s[find(a)], p[find(a)] = find(b);
        }
        else if(command == "Q1")
        {
            cin >> a >> b;
            find(a) == find(b)? cout << "Yes" << endl : cout << "No" << endl;
        }
        else if(command == "Q2")
        {
            cin >> a;
            cout << s[find(a)] << endl;
        }
    }
    return 0;
}