#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<unordered_map>
#include<map>
#define sort stable_sort
#define map unordered_map
using namespace std;
typedef long long ll;

int n, m;
int op;
int fa[10010];

int getf(int now){
    if(fa[now] == now){
        return now;
    }
    fa[now] = getf(fa[now]);
    return fa[now];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    int x, y;
    for(int i = 1; i <= n; i++){
        fa[i] = i;
    }
    for(int i = 1; i <= m; i++){
        cin >> op >> x >> y;
        if(op == 1){
            int now = getf(x);
            fa[now] = getf(y);
        }else{
            if(getf(x) == getf(y)){
                cout << "Y" << endl;
            }else{
                cout << "N" << endl;
            }
        }
    }
    return 0;
}

模板题P3367，但是求这份代码的最劣复杂度

从我自己的主观上来说是 $O(nm)$ 的，但是注意到 getf 函数里有这么一句话 fa[now] = getf(fa[now]);，所以按理来说不可能所有时候并查集都是一条链，所以这份代码的复杂度是多少捏

谢谢