글 읽기 - 시간복잡도 상으로는 경로 압축이 필요 없지 않나요?

dohoon 3년 전 0

위쪽이 경로 압축을 한 코드,

아래쪽이 경로 압축을 하지 않은 코드입니다.

위쪽은 제대로 나오는 것이 이해가 됩니다... 무척 빠르니까요.

근데, 경로 압축을 쓰지 않더라도 O(m log n) ~~O(n log m)~~ ~ O(10⁷)이니까 나와야 하지 않나요?

혹시나 해서 ios::sync_with_stdio(0); cin.tie(0);도 했습니다...

#include <bits/stdc++.h>
#define same(a, b) (find(a) == find(b))
using namespace std;
const int maxn = 1000000;
int sz[maxn+1], link[maxn+1];

//경로 압축 함
int find(int x) {
    if (x == link[x]) return x;
    return link[x] = find(link[x]);
}
//경로 압축 하지 않음
int _find(int x) {
    while (x != link[x]) x = link[x];
    return x;
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b];
    link[b] = a;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 0; i <= n; ++i) {
        sz[i] = 1;
        link[i] = i;
    }
    while (m--) {
        bool x; int a, b;
        cin >> x >> a >> b;
        if (x) cout << (same(a, b) ? "YES" : "NO") << '\n';
        else if (!same(a, b)) unite(a, b);
    }
}