백준 1717 집합의 표현

문제 설명

1717 문제 링크
입력이 0 1 2라고 주어지면 1이 포함된 집합과 2가 포함된 집합 합치기
입력이 1 2 3라고 주어지면 2, 3이 같은 집합이면 YES 아니라면 NO 출력

문제 풀이

집합에 포함이 된다? → 같은 부모로 묶여있다. → Union-find

골드 문제에 정답 비율도 낮아서 단순히 union-find로 풀면 시간초과나 놓친 반례가 있을 것이라 생각했는데 그냥 맞았다...ㅎㅎ

소스 코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> parent;

int find_parent(int a){
    if(a==parent[a]){
        return a;
    }else{
        return parent[a] = find_parent(parent[a]);
    }
}

void union_group(int a,int b){
    int pa = find_parent(a);
    int pb = find_parent(b);
    if(pa!=pb){
        parent[pb]=pa;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, o, s, e;
    cin >> n >> m;
    parent.resize(n + 1);
    for (int i = 0; i <= n; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < m; i++) {
        cin >> o >> s >> e;
        if (o == 0) {
            union_group(s, e);
        } else {
            if (find_parent(s) == find_parent(e)) {
                cout << "YES" << '\n';
            } else {
                cout << "NO" << "\n";
            }
        }
    }

    return 0;
}