[백준] 1717번 집합의 표현

 

[적용한 알고리즘]

Disjoint-set, 유니온 파인드 (뭐가 맞는 표현인지 잘모름)

 

[아이디어]

유니온 파인드 문항의 기본 예제

 

[생각의 흐름 / 절차] 

[교훈]

나중에 크루스칼 알고리즘이나 이런 곳에 많이 쓰이니 잘 익혀두자.

find 함수에서 메모이제이션 같은 느낌이 들어가는 곳이 시간 단축에 큰 도움이 된단다.

 

<코드>

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 1000001
using namespace std;

int p[MAX];
int find(int n){
    if (n == p[n]) return n;
    return p[n] = find(p[n]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);

    if (a == b) return;
    p[a] = b;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i <= n; i++) p[i] = i;

    for (int i = 0; i < m; i++){
        int oper, a, b;
        scanf("%d %d %d", &oper, &a, &b);

        if (oper == 1){
            if (find(a) == find(b)) printf("YES\n");
            else printf("NO\n");
        }
        else merge(a, b);
    }

    return 0;
}