(C++) - 백준(BOJ) 1717번 : 집합의 표현

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

1717번: 집합의 표현

union-find로 풀었습니다.

 

 

 

📕 풀이방법

📔 입력 및 초기화

 1. 입출력이 많으니 c와의 동기화를 풀어줍니다.

 

 2. n, m을 입력해줍니다.

 

 3. parent배열을 선언해줍니다. 처음에 i번 원소의 부모는 자기 자신입니다. 이때 번호가 1번부터 시작하므로 n번째까지 loop를 돌며 초기화해줘야 합니다.

 

 3. m번동안 op, a, b를 입력해주며 실행합니다.

 

📔 풀이과정

두 집합을 하나로 합침, 두 집합이 같은지의 여부는 union, find로 각각 대입해 생각할 수 있습니다. 같은 집합에 속한다는 것은 parent가 같다는 의미입니다. 

 1. op == 0일 때

 merge(a,b)

 

 2. op == 1

find(a) == find(b)라면 YES 아니라면 NO를 출력합니다.

 

---

📕 Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int parent[1000001], n, m;

int find(int x){
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);
    parent[a] = b;
}

int main(){
    fastio;
    cin >> n >> m;
    for(int i = 0; i <= n; i++) parent[i] = i;
    while(m--){
        int op, a, b;
        cin >> op >> a >> b;
        if(!op) merge(a,b);
        else {
            if(find(a) == find(b)) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}