[백준 1717] 집합의 표현

0. 제목

• 백준 1717 집합의 표현
• BOJ 1717 집합의 표현
• C++ 1717 집합의 표현

---

1. 문제

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

---

2. 풀이

• Union-Find방식을 사용하는 문제이다.
• Find를 통해 root를 찾아주고 Union을 통해 합쳐준다. union은 merge로 구현하였다.
• 0과 1이 입력되는 케이스를 구분하여 적절히 find, union을 수행해주면 된다.

---

3. 코드

#include <iostream>
using namespace std;
 
int parent[1000001];
 
int find(int x){
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}
 
void merge(int u, int v){
    u = find(u);
    v = find(v);
    if(u != v)
        parent[u] = v;
}
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    
    for(int i = 0; i <= n; i++)
        parent[i] = i;
    
    for(int i = 0; i < m; i++){
        int num, a, b;
        cin >> num >> a >> b;
        
        if(num == 0){
            merge(a, b);
        }
        else if(num == 1){
            if(find(a) == find(b))
                cout << "YES" << '\n';
            else
                cout << "NO" << '\n';
        }
    }
    
    return 0;
}