[Union-find] BOJ 1717 집합의 표현

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

1717번: 집합의 표현

 

문제 해결 알고리즘

 

Union find 문제

 

parent 배열이 무조건 그 노드의 조상노드를 가리키는 게 아니기 때문에 조상 노드 비교 해줄 때는 find_parent 함수를 써줘야한다.

 

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int n, m;
int parent[1000001];

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

void unionVertex(int a, int b){

    a = find_parent(a);
    b = find_parent(b);

    if(a == b) return;
    else parent[a] = b;
    
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;

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

    int k, a, b;
    for(int i=0;i<m;i++){
        cin >> k >> a >> b;

        if(k == 0) {
            if(a == b) continue;
            if(a > b) swap(a, b);
            unionVertex(a, b);
        }
        else {
            if(find_parent(a) != find_parent(b)) cout << "NO\n";
            else cout << "YES\n";
        }
    }
}