백준 1717번: 집합의 표현

문제

문제 바로가기> 백준 1717번: 집합의 표현

풀이

Union-Find 알고리즘을 이용하여 문제를 풀었다.
Union-Find: Disjoint set(서로 중복되지 않는 부분 집합들로 나눠진 원소 정보를 저장/조작하는 자료구조)을 표현할 때 사용하는 알고리즘

#include<iostream>
using namespace std;

int root[1000001];

int find_(int x){
    if(root[x]==x) return x;
    return root[x] = find_(root[x]); // 경로 단축
}

void union_(int a, int b){
    root[find_(a)] = find_(b);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, m; cin>>n>>m;
    for(int i=0; i<=n; i++) root[i] = i;
    for(int i=0; i<m; i++){
        int oper, a, b; cin>>oper>>a>>b;
        if(oper == 0) union_(a, b);
        else if(find_(a)==find_(b)) cout << "YES\n";
        else cout << "NO\n";
    }
}