유니온파인드

base : https://www.acmicpc.net/problem/1717 

처음에 memset(-1)을 해두고, p[i]의 절대값이 집합의 원소의 개수가 되도록 구현했다.

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

class UF {

   public:

    vector<int> p;

    UF(int n) { p = vector<int>(n + 1, -1); }

    int find(int cur) {

        if (p[cur] < 0) return cur;

        return p[cur] = find(p[cur]);

    }

#define union _union

    void union(int A, int B) {

        A = find(A), B = find(B);

        if (A == B) return;

        if (p[A] < p[B])

            p[A] += p[B], p[B] = A;

        else

            p[B] += p[A], p[A] = B;

    }

};

int n, m;

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    cin >> n >> m;

    int i;

    auto uf = UF(n);

    for (i = 0; i < m; i++) {

        int op, a, b;

        cin >> op >> a >> b;

        if (op == 0)

            uf.union(a, b);

        else if (op == 1)

            cout << (uf.find(a) == uf.find(b) ? "YES" : "NO") << '\n';

    }

    return 0;

}

---