[BOJ] 집합의 표현

[문제]

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

1717번: 집합의 표현

[풀이]

 

1717

맞았습니다!!

5896

44

C++14 / 수정

853

6초 전

 

1) union-find를 사용하여 해결한다. 

 

2) init()에서 부모를 초기화 한다. (n의 수만큼)

 

3) find()에서는 각 원소가 속한 부모를 찾아서 반환한다. 

만약 현재 원소가 부모라면 리프노드이기 때문에 그냥 원소가 집합이 된다. 

 

4) union_find는 각 원소들의 부모노드를 찾아 '부모노드를' 이어준다. 

 

---

#include <iostream>
#include <vector>
 
#define MAX_N 1000001
using namespace std;
 
//집합의 표현 
vector<int> parent(MAX_N);
 
///////////union-find ///////////
void init(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
}
 
int find(int a) {
    if (parent[a] == a) return a;
 
    else{
        return parent[a] = find(parent[a]);
    }
}
void union_find(int a, int b) {
    int roota = find(a);
    int rootb = find(b);
 
    parent[roota] = rootb;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
 
    cin >> n >> m;
 
    init(n); //부모노드 세팅 
 
    int op, a, b;
 
    for (int i = 0; i < m; i++) {
        //연산 횟수만큼 반복 
        cin >> op >> a >> b;
 
        if (op == 0) {
            //합집합 
            union_find(a, b);
 
        } else if (op == 1) {
            if (find(a) == find(b)) {
                cout << "YES\n";
            }
            else 
                cout << "NO\n";
        }
    }
    return 0;
}