분리 집합(Union-Find)을 이용해서 해결해야 할 문제였지만 분리 집합 해결법을 떠올리지 못하였다.

정답

출처

#include<iostream>
#include<vector>

using namespace std;
int n, m;
int parent[1000001];

int getParent(int x) {
    if (parent[x] == x) return x;
    return parent[x] = getParent(parent[x]);
}
void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a > b) parent[a] = b;
    else parent[b] = a;
}
void findParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a == b) cout << "YES\n";
    else cout << "NO\n";
}


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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < m; i++) {
        int o, a, b;
        cin >> o >> a >> b;
        if (!o) {// union연산
            unionParent(a, b);
        }
        else { //find연산
            findParent(a, b);
        }

    }

    return 0;
}

오답

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>


#define endl "\n"

using namespace std;
int n, m; 
vector<int> jib[1000000];


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

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int f, a, b;
        cin >> f >> a >> b;

        if (f == 0) {
            if (a == b) {
                jib[a].push_back(b);
            }
            else {
                jib[a].push_back(b);
                jib[b].push_back(a);
            }
        }

        // 1 2
        // 1 3
        // 2 3

        else if (f == 1) {
            if (find(jib[a].begin(), jib[a].end(), b) == jib[a].end() && find(jib[b].begin(), jib[b].end(), a) == jib[b].end() ) {
                cout << "NO" << endl;
            }
            else {
                cout << "YES" << endl;
            }
        }
    }

    return 0;

}